Merging Overlapping Intervals

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
 If you are a student, email to admin@thealgorists.com to get special student discount.
Here we are interested in merging any two overlapping intervals into one interval. For example, if there are intervals 1 > 4, 3 > 10, 5 > 7, 8 > 16, then they all should be merged together to become one interval 1 > 16 because there are two or more intervals that overlap.
 1 > 4, 3 > 10 overlap with each other, so they merge to give 1 > 10.
 Then we have the interval 5 > 7. From previous step we got merged interval 1 > 10. Since 5 > 7 and 1 > 10 are overlapping, they merge to give 1 > 10.
 Then 1 > 10 and 8 > 16 merge to yield 1 > 16
Now let's take another example, 1 > 4, 20 > 22, 3 > 10, 25 > 35, 35 > 40, 39 > 61, 5 > 7, 8 > 16.
Here, 1 > 4, 3 > 10, 5 > 7, 8 > 16 merge together to yield 1 > 16 ,
20 > 22 has no overlap with any other intervals,
and 25 > 35, 35 > 40, 39 > 61 overlap and merge to yield 25 > 61
Output: 1 > 16, 20 > 22, 25 > 61.
The above discussed problem can be solved in different ways as discussed below:
Let's define the Interval class as below:
public class Interval {
public int start;
public int end;
}

Connected Components:
We can use Connected Components concept from graph theory to solve this problem. We can make a graph out of all the intervals, treating each interval as nodes. The overlapping intervals would make Connected Components. we then do graph traversal of each connected component, discover all overlapping intervals and merge them. make connected compo Algorithm:

Treat each intervals as a node in a graph.

Build Graph:
We would represent graph as adjacency lists.
For each interval, we iterate over all other intervals and whenever we find an overlapping interval we add them in the adjacency list .
For any interval which has no overlapping intervals, we out an empty list as adjacency list.
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Time Complexity for Build Graph operation: O(n^2). n = total number of intervals.
Space Complexity for this operation: O(n^2).
In worst case, every interval is overlapping with every other intervals.

Find the Connected Components:
How do we find the connected components in the graph?
Image Source: https://www.cs.cornell.edu/courses/cs2112/2012sp/lectures/lec24/components.png
If you try to visualize the graph now, the connected components will seem like island. The graph will be consisting of one or more disjoint sets or connected components. The graph in the picture above has 3 connected components. Each disjoint set consists of connected nodes. So we need to basically do a graph traversal of each of these disjoint sets (or, islands) or connected components and discover all the connected nodes in the connected components. So how can we achieve this? Simple, graph traversal like DFS or BFS.
For our implementation let's go with DFS.
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Time Complexity to build Connected Components: O(n). We are visiting each interval only once.

For each Connected Components Merge all the intervals in the connected component into one.
To merge all the overlapping intervals from each connected component we just need to create one merged interval for which the start value will be the minimum of the start values of all the overlapping intervals in the currnt connected component, and the end value will be the maximum of the the end values of all the overlapping intervals in the current connected component.private int[] merge(List
intervals) { int[] res = intervals.get(0); for (int i = 1; i < intervals.size(); i++) { res[0] = Math.min(res[0], intervals.get(i)[0]); res[1] = Math.max(res[1], intervals.get(i)[1]); } return res; }
Time Complexity for Merge operation: O(n)
Complete Code:
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Overall Time Complexity = O(n^2) + O(n) + O(n) = (n^2)
Overall Space Complexity = O(n^2)


Sweep Line Algorithm:
We sort the intervals on the start value of the intervals and using LinkedList.
This approach is much more straight forward. We sort all the intervals on their start values, and then iterate over the sorted list of intervals. At every interval we look at the previous interval, and see if the start value is less than or equal to the end value of the previous interval. If yes, we merge these two intervals. If not we add this interval.
What data structure to use? Let's see. We need to have easy access to the last element in the data structure all the time. LinkedList would serve our purpose very well, as accessing tail is very convenient. We will go on adding any new interval, that needs to added, at the end of the linked list.
public List<Interval> merge(List<Interval> intervals) { Collections.sort(intervals, new Comparator<Interval>(){ public int compare(Interval a, Interval b) { return a.start < b.start ? 1 : a.start == b.start ? 0 : 1; } }); LinkedList<Interval> merged = new LinkedList<Interval>(); for (Interval interval : intervals) { // if the list of merged intervals is empty or if the current // interval does not overlap with the previous, simply append it. if (merged.isEmpty()  merged.getLast().end < interval.start) { merged.add(interval); } // otherwise, there is overlap, so we merge the current and previous // intervals. else { merged.getLast().end = Math.max(merged.getLast().end, interval.end); } } return merged; }
Time Complexity => O(nlogn) for sorting + O(n) for iterating = O(nlogn)
Space Complexity = O(1) , sorting is inplace.
Related MustRead Topics:
 1d Range Search
 Closest Pair
 Convex Hull

Dual Line Sweep
& Rectangles Union 
2D Intervals Union
& Skyline Problem  Overlapping 1D Intervals
 Separating Overlapping 1D Intervals
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn