Skip to content
JsDevLife
Menu
  • Home
  • Leetcode in JS
  • About me
  • Contact Us
Menu

A solution to LeetCode Problem 56. Merge Intervals in JavaScript

Posted on December 19, 2022July 30, 2023 by Vikas Kad

 

A solution to LeetCode Problem 56. Merge Intervals in JavaScript

 

In this problem, we are given an array of intervals, where each interval is an object with a start and end property. The intervals are not necessarily sorted. Our task is to merge any overlapping intervals and return the resulting array of intervals.

Problem Statement:

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104 

Solution

To solve this problem, you can use a greedy approach, where you first sort the intervals based on the start time, and then you can merge the overlapping intervals one by one. Here is a JavaScript solution that demonstrates this approach:
function merge(intervals) {
  if (!intervals.length) return intervals;

  // sort intervals by start time
  intervals.sort((a, b) => a[0] - b[0]);

  // initialize the merged intervals with the first interval
  let merged = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    let currentInterval = intervals[i];
    let lastMergedInterval = merged[merged.length - 1];

    // if the current interval overlaps with the last merged interval, merge them
    if (currentInterval[0] <= lastMergedInterval[1]) {
      lastMergedInterval[1] = Math.max(lastMergedInterval[1], currentInterval[1]);
    } else {
      // otherwise, add the current interval to the merged intervals
      merged.push(currentInterval);
    }
  }

  return merged;
}

This solution has a time complexity of O(n * log(n)), since the intervals are sorted using the built-in Array.sort() function, which has a time complexity of O(n * log(n)). The space complexity is O(n), since we create a new array to store the merged intervals.

 

I hope this helps! Let me know if you have any questions or suggestions for improvement.

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Recent Posts

  • Solving LeetCode Problem 79 – Word Search in JavaScript
  • Solving LeetCode Problem 48: Rotate Image using JavaScript
  • Solving the “Container With Most Water” LeetCode Problem in JavaScript – A Comprehensive Guide
  • LeetCode Solution: 54: Spiral Matrix in JavaScript
  • Solution to LeetCode Problem 31. Next Permutation in JavaScript

Archives

  • 2023 (5)
  • 2022 (20)
  • 2021 (2)
  • 2020 (4)
  • 2019 (14)
  • 2018 (17)

Categories

  • blockchain development
  • Blog
  • crystal
  • flutter
  • flutter.io
  • GitHub
  • Installation
  • Ionic Framework
  • javascript
  • leetcode-in-js
  • masteringInJavasript
  • mcqs
  • MongoDB
  • nodejs
  • Object Oriented Javacript
  • python
  • smart contracts
  • visual studio

Quick Links

  • Home
  • Leetcode in JS
  • About me
  • Contact Us

Terms of service

  • Terms Of Service
  • Disclaimer
©2023 JsDevLife | Design: Newspaperly WordPress Theme