Merge an Array With Overlapping Intervals

Statement#

We’re given an array of interval pairs as input where each interval has a start and end timestamp. The input array is sorted by starting timestamps. Merge the overlapping intervals and return a new output array.

Example#

Consider the input array below. Intervals (1, 5), (3, 7), (4, 6), (6, 8) are overlapping, so they should be merged to one big interval (1, 8). Similarly, intervals (10, 12) and (12, 15) are also overlapping and should be merged to (10, 15).

Sample input#

intervals = [[1,3],[2,6],[8,10],[15,18]]

Expected output#

[[1,6],[8,10],[15,18]]

Try it yourself#

Solution#

This problem can be solved in a simple linear scan algorithm. We know that the input is sorted by starting timestamps. Here is the approach we are following:

• Using the given list of input intervals, we keep merged intervals in the output list.
• For each interval in the input list:
  • If the input interval is overlapping with the last interval in the output list, then we merge these two intervals and update the last interval of the output list with the merged interval.
  • Otherwise, we add an input interval to the output list.

Below is a visual run-through of the above explanation:

The green interval in the input list represents the selected input interval. The last interval in the output list is green. Either it is updated by merging this interval and selected input interval or appending input interval.

Time complexity#

The time complexity of this solution is linear, $O(n)$.

Space complexity#

The space complexity of this solution is linear, $O(n)$.

Note: This is the worst case when there are non-overlapping elements in the array.