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

In the example above the intervals happen to be sorted by the first value of each interval. This might not necessarily be the case with other inputs so first we have to sort the original input array. We can do this using JavaScripts built in sort method which will run in O(n log n) time.

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

Next we want to create a new array that we will add the merged intervals to. To begin with, we want to add the first interval from the original array of intervals.

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

Next we use a for loop to iterate through the sorted array. We start the for loop at the second interval (index 1) because we have already adding the first interval. From there we use an “if else” conditional to check if the beginning value of the current interval is less than or equal to the end value of the last interval that was added to the results array.

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.