Problem Statement
Given a list of non-overlapping intervals sorted by their start time, insert a given interval at the correct position and merge all necessary intervals to produce a list that has only mutually exclusive intervals.
Example 1:
Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,6]
Output: [[1,3], [4,7], [8,12]]
Explanation: After insertion, since [4,6] overlaps with [5,7], we merged them into one [4,7].
Example 2:
Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,10]
Output: [[1,3], [4,12]]
Explanation: After insertion, since [4,10] overlaps with [5,7] & [8,12], we merged them into [4,12].
Example 3:
Input: Intervals=[[2,3],[5,7]], New Interval=[1,4]
Output: [[1,4], [5,7]]
Explanation: After insertion, since [1,4] overlaps with [2,3], we merged them into one [1,4].
Constraints:
- 1 <= intervals.length <= 10<sup>4</sup>
intervals[i].length == 2- 0 <= start<sub>i</sub> <= end<sub>i</sub> <= 10<sup>5</sup>
intervalsis sorted by starti inascendingorder.newInterval.length == 2- 0 <= start <= end <= 10<sup>5</sup>
Why this is a Merge Intervals problem
| What the question says | The signal it matches |
|---|---|
| "Given a list of non-overlapping intervals sorted by their start time" | the input is a list of pairs, already in the order this pattern needs |
| "merge all necessary intervals to produce a list that has only mutually exclusive intervals" | the wording includes merge, and the output is a set of non-overlapping blocks |
| comparing the new interval against every existing one | your first idea is to compare every pair of intervals |
Walking the list once and folding the overlapping stretch into a single block is the merge into blocks variant.
The closest alternative. The habit from Merge Intervals is to sort first. Read the first line again. The input is already "sorted by their start time" and already non-overlapping.
Sorting again turns a linear pass into an O(N log N) one for no gain. The answer has three parts. They are the intervals ending before the new one, the merged middle, and the intervals starting after it.
Solution
If the given list was not sorted, we could have simply appended the new interval to it and used the merge() function from Merge Intervals. But since the given list is sorted, we should try to come up with a solution better than O(N * logN).
When inserting a new interval in a sorted list, we need to first find the correct index where the new interval can be placed. In other words, we need to skip all the intervals which end before the start of the new interval. So we can iterate through the given sorted listed of intervals and skip all the intervals with the following condition:
intervals[i].end < newInterval.start
Once we have found the correct place, we can follow an approach similar to Merge Intervals to insert and/or merge the new interval. Let's call the new interval a and the first interval with the above condition b. There are five possibilities:
The diagram above clearly shows the merging approach. To handle all four merging scenarios, we need to do something like this:
c.start = min(a.start, b.start) c.end = max(a.end, b.end)
Step-by-Step Algorithm
- Create an empty list to store the merged intervals.
- Traverse the given list of intervals:
- Add all intervals that end before the new interval starts to the merged list.
- For overlapping intervals:
- Adjust the start of the new interval to the minimum start time.
- Adjust the end of the new interval to the maximum end time.
- Add the merged new interval to the merged list.
- Add all intervals that start after the new interval ends to the merged list.
- Return the merged list of intervals.
Algorithm Walkthrough
The list [1, 3], [5, 7], [8, 12] is already sorted and has no overlaps, and [4, 6] is being inserted. The existing intervals fall into three groups: those entirely before the new one, those that overlap it, and those entirely after.
1 of 5
Code
Here is what our algorithm will look like:
Time Complexity
As we are iterating through all the intervals only once, the time complexity of the above algorithm is O(N), where N is the total number of intervals.
Space Complexity
Ignoring the space needed for the result list, the algorithm runs in constant space O(1).
If we include the result list, the space complexity will be O(N) as we need to return a list containing all the merged intervals.