Merge Intervals Solution In JavaScript

The Merge Intervals problem provides us with an array of intervals. The intervals are given as arrays of two elements where the first element is beginning value of the interval and the second element is the end value. We then have to combine the intervals which have overlapping values.

Here is an example of an input and the desired result.

The first two intervals are overlapping so we merge them into one interval. The first interval ends with the value of 3 and the second interval starts with the value of 2. Because 2 is less than 3 these intervals are said to overlap. If the first two intervals were [1,3] and [3,7] that would still be considered overlapping and would be merged to [1,7]. The rest of the intervals in the array do not overlap so they are left as is.

Sorting

We want to sort the array in ascending order based on the beginning value of each interval. This is done by comparing the intervals at the 0 index.

Results Array

We take the interval at index 0 and add its beginning value and end value (index 0 and 1) to an array within the results array.

For Loop With Conditionals

If this results in true, we want to alter the end value of the last interval in the results array. We wouldn’t necessarily want to just change end value of the previous interval to the end value of the current interval. For example, if the previous interval is [1,8] and the current interval is [2,7] this would make the result interval [1,7] instead of the correct [1,8]. We can account for this by using the Math.max function to check to see which interval has the greatest ending value.

If the beginning value of the current interval is greater than the ending value of the previous interval, then we simply push that interval to end of the results array.

Because we are comparing each current interval to the last interval that was added to the results array (as opposed to the previous interval in the original array) we are accounting for multiple intervals being merged. For example [1,4], [3,5], and [4,7] would all get merged to a single interval [1,7].

After we iterate through the entire sorted array of original intervals we return our results array which now contains all the merged intervals.

Here is the final solution.

The overall time complexity would be O(n log n) because of the sorting method and the space complexity would be O(n) because we are creating a new results array.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store