Solution: Merge Intervals

Statement#

We are given an array of closed intervals, intervals, where each interval has a start time and an end time. The input array is sorted with respect to the start times of each interval. For example, intervals = $[~[1,4], ~[3,6], ~[7,9]~]$ is sorted in terms of start times $1, ~3$, and $7$.

Your task is to merge the overlapping intervals and return a new output array consisting of only the non-overlapping intervals.

Constraints:

• $1 \leq$ intervals.length $\leq 10^4$
• intervals[i].length $= 2$
• $0 \leq$ start time $\leq$ end time $\leq 10^4$

Solution#

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow, based on considerations such as time complexity and any implementation constraints.

Naive approach#

The naive approach is to start from the first interval in the input list and check for any other interval in the list that overlaps it. If there is an overlap, merge the other interval into the first interval and then remove the other interval from the list. Repeat this for all the remaining intervals in the list.

In the worst-case scenario, where all intervals overlap with each other, we would need to traverse the input list multiple times to merge all the overlapping intervals. If we have $n$ intervals in the input list, the time complexity to traverse and merge these would be $O(n^2)$. However, the space complexity for this solution is $O(1)$, since we are not using any extra processing space.

Optimized approach using merge intervals#

This problem illustrates the characteristic features of the merge intervals pattern. Therefore, to solve this problem, we need to handle all the six ways in which any two given intervals relate to each other. Before jumping onto the solution, let’s review all these ways using the illustration from the introduction to this pattern:

Note: In the slides above, if we notice, there is something common among all the scenarios of overlapping intervals. If we call ‘a’ the first interval and ‘b’ the second interval, then in all the overlapping scenarios, the start time of the second interval always occurs before the end time of the first interval, that is, $b's ~start ~time$ $<$ $a's ~end~time$.

In this solution, we use the merge intervals pattern with a simple linear scan to merge the overlapping intervals. First, we create an output list and copy the first interval of the input list to it. Next, we traverse the remaining intervals of the input list and check whether any interval overlaps with the interval present in the output list. If they overlap, update the interval in the output list. Otherwise, add the current input interval to the output list. Repeat this for all the intervals in the input list. Please note that when we have more than one interval in the output list, we compare the input intervals with the last interval of the output list.

Now, let’s look at the following illustration to get a better understanding of the solution:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to the “Just the code” section.

Step-by-step solution construction#

The first step is to copy the first interval from the input list to the output list. Next, add a loop to traverse the remaining intervals in the input list. In each iteration, we will use the variable cur_start to store the start time and the variable cur_end to store the end time of the current input interval. Moreover, to keep track of the end time of the last interval in the output list, we create a variable, prev_end. These variables will help us identify any overlapping intervals in the later steps.

The code below implements the steps above:

Inside the loop, we check each interval of the input list against the last interval of the output list. For each interval in the input list, we do the following:

• If the current input interval is overlapping with the last interval in the output list, we merge these two intervals and replace the last interval of the output list with the newly merged interval.
• Otherwise, we add the input interval to the output list.

To check if the current input interval and the last interval in the output list overlap, we’ll check the start time of the current interval and the end time of the last interval in the output list. If the start time of the current interval is less than the end time of the last interval in the output list, that is, curr_start $<=$ prev_end, the two intervals overlap. Otherwise, they don’t overlap. Since the intervals are sorted in terms of their start times, we won’t encounter cases where the current interval’s start and end times are less than the start time of the last interval in the output list.

For example, if we have an input interval list $[~ [1,5], ~[3,7]~ ]$, we will first add the interval $[1,5]$ to the output list. Then, we will check $[3,7]$ from the input list against the last interval in the output list, $[1,5]$, to check if they overlap or not. The start time, 3, of the current interval is less than the end time, 5, of the last interval in the output list, so the two intervals overlap. Since these two intervals overlap, we will merge them and update the last interval of our output list to $[1,7]$.

The lines highlighted below implement this logic:

Just the code#

Here’s the complete solution to this problem:

Solution summary#

To recap, the solution to this problem can be divided into the following two parts:

1. Insert the first interval from the input list into the output list.

2. Traverse the input list of intervals. For each interval in the input list, we do the following:

   • If the input interval is overlapping with the last interval in the output list, merge these two intervals and replace the last interval of the output list with this merged interval.
   • Otherwise, add the input interval to the output list.

Time complexity#

The time complexity of this solution is $O(n)$, where $n$ is the number of intervals in the input list.

Space complexity#

The space complexity of this solution is $O(1)$, since we only use constant space other than the input and output data structures.