Understanding interval merging pattern
Some interval problems require merging all the overlapping intervals in a given array into a single interval that covers all the merged intervals. There are a few brute-force solutions to this problem using nested loops, but all of them are complicated and inefficient. For problems like these, we can use the line sweep technique to merge all the overlapping intervals in the array in a single pass.
Merged overlapping intervals from an array of intervals.
In this lesson, we will learn more about using the line sweep technique to merge all overlapping intervals in an array.
Interval merging technique
Consider we are given an array of intervals arr where each item in the array is a pair of an interval's start and end coordinates. The first step in merging the intervals is to sort the array in a non-decreasing order of the start coordinates of intervals. In case two intervals have the same start coordinate, we sort them by their end coordinates.
Sort the given intervals in a non-decreasing order of start coordinates.
We then create another array merged to store all the merged intervals and initialize it with the first interval in the now-sorted arr. These arrays can be viewed geometrically as intervals on the x-axis of a cartesian plane, and we can now apply the line sweep technique to merge the overlapping intervals in a single pass. As we will see later, we expand the last interval of the merged when we see an overlapping interval in arr to merge it.
Create a new array merged and initialize it with the first interval of arr.
We then iterate in the arr starting from the second interval and check if it intersects with the last interval in the merged array. If the start coordinate of the interval in arr lies between the start and end coordinates of the last interval in merged, it means they intersect and should be merged. We merge them by updating the end coordinate of the last interval in merged to the end coordinate of the interval in arr if it is greater. We repeat this process until we find a non-intersecting interval.
If, at any point, we reach an interval that does not intersect with the last interval in merged, we append that interval to merged to make it the new last interval in merged which will expand to merge further intervals from arr. This process is repeated until we reach the end of arr at which point we will have the merged intervals in merged.
Traverse arr from index 1 and expand last interval of merged array to merge overlapping intervals.
At the end of all iterations, all overlapping intervals in arr will be merged in the merged array.
Algorithm
The algorithm given below outlines the generic interval merging technique.
- Step 1: Sort the input array `arr` by the start coordinate of intervals
- Step 2: Create a list `merged` to store the merged intervals and initialize it with the first interval from sorted `arr`.
- Step 3: Iterate in `arr` starting from the second item:
- Step 3.1: If the start coordinate of the interval in `arr` lies between the start and end coordinates of the last interval in `merged`, set the end coordinate of `merged` to the end coordinate of the interval in `arr` it it is greater:
- Step 3.2: If the interval in `arr` does not intersect with the last interval in `merged`, append the interval in `arr` to `merged`
Implementation
Given below is the generic code implementation of the generic interval merging technique using the array merged. Note that in this implementation, if the end of one interval coincides with the start of another, we consider them overlapping.
C++
Java
Typescript
Javascript
Python
Complexity Analysis
To merge the intervals, we need to sort the interval array by the start coordinate, an O(NlogN) operation where N is the array's size. We only traverse the array after that, which takes linear O(N) time, so the time complexity is O(NlogN) in any case.
Since we create an additional array to store the merged intervals, the best case is if all intervals merge together into a single interval, in which case, the merged array will only have a single interval that uses constant O(1) space. In the worst case, there may be no overlap between any intervals, and so the merged array will have all the same intervals as the original array, which will have linear O(N) space.
Best Case: All intervals overlap
- Space Complexity - O(1)
- Time Complexity - O(NlogN)
Worst Case: No interval overlaps
- Space Complexity - O(N)
- Time Complexity - O(NlogN)