Merge Intervals

Patrick Leaton
Published: June 27, 2021, 4:23 p.m.
Problem Description

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] overlaps, 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 <= 10^4
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 10^4

 

The description was taken from https://leetcode.com/problems/merge-intervals/.

Problem Solution

#O(N(Log N)) Time, O(1) Space
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key = lambda i: i[0])
        output = [intervals[0]]
        for start, end in intervals[1::]:
            previous_end = output[-1][1]
            if start <= previous_end:
                output[-1][1] = max(previous_end, end)
            else:
                output.append([start,end])
        return output

Problem Explanation

This problem pretty much boils down to, "Where are the overlaps in intervals that we need to merge?".  How would we solve that?

What would help is if we could order the start times in a linear fashion then step through each interval and ask, "Is the previous interval's end-time overlapping with the current start time?"

That is how we will solve this problem.

Let's take the test case, for example, [[1,4],[2,3],[8,10]].

We will draw out our timeline below, this is a recommended approach for interval questions.

 

<--1--2--3--4--5--6--7--8--9--10-->

 

Now let's add our intervals.

 

                    
                                                
<--1--2--3--4--5--6--7--8--9--10-->
 
 

 

As we can see from the timeline, the first and second intervals are overlapping. 

Here is what we will do.

 We will sort our intervals by each interval's start time.

        intervals.sort(key = lambda i: i[0])

 

Next, we will add the first interval to the output since there couldn't possibly be an interval that started before this one that would have an overlapping end-time.

        output = [intervals[0]]

 

Then, for the remainder of the intervals, we will look at the previous end-time and compare it to the current start time.

If the previous end time is greater or equal to the current start time, since the description says equal start/end times are considered overlapping as well, we will merge the current interval into the previous one that is already saved to the output.  

We need to be careful that we keep the appropriate end time.  Refer back to our example, the second interval actually ends before the first one.  To handle this, we will take the maximum end-time between the two.

        for start, end in intervals[1::]:
            previous_end = output[-1][1]
            if start <= previous_end:
                output[-1][1] = max(previous_end, end)

 

If there is no overlap between the current interval and the previous, we will just append the current interval to the output because we won't need to merge it.

            else:
                output.append([start,end])

 

Once we have traversed the intervals and merged the ones we needed to, we will return the output.

        return output