Merge Overlapping Intervals

Problem

Given a collection of intervals, merge all overlapping intervals.

Input - Collection of intervals
Output - Collection of mutually exclusive intervals after merging

Example

Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Solution

Method 1 - Brute force
A simple approach is to start from the first interval and compare it with all other intervals for overlapping, if it overlaps with any other interval, then remove the other interval from list and merge the other into the first interval. Repeat the same steps for remaining intervals after first. This approach cannot be implemented in better than O(n^2) time.

Method 2 -  Sort on the basis of start time and merge

An efficient approach is to first sort the intervals according to starting time. Once we have the sorted intervals, we can combine all intervals in a linear traversal. The idea is, in sorted array of intervals, if interval[i] doesn’t overlap with interval[i-1], then interval[i+1] cannot overlap with interval[i-1] because starting time of interval[i+1] must be greater than or equal to interval[i].
Following is the detailed step by step algorithm :

1. Sort the intervals based on increasing order of starting time.
2. Select the first element from the collection of intervals. Lets call it A
3. For each interval in the collection do the following
   1. If the current interval does not overlap with the A,do nothing.
   2. If the current interval overlaps with A and ending time of current interval is more than that of stack top, update stack top with the ending time of current interval. Put it in new list called result
4. At the end result collection will contain the merged intervals.

Code in java
In java, we can sort any object provided we write implement the comparator interface. Then we can simply use Collections. sort() utility. You can sort the intervals in other languages, in some other way. So, lets stay language agnostic. I just wanted to update you that.

class Interval {
 int start;
 int end;
 
 Interval() {
  start = 0;
  end = 0;
 }
 
 Interval(int s, int e) {
  start = s;
  end = e;
 }
}

class IntervalComparator implements Comparator<Interval> {
 public int compare(Interval i1, Interval i2) {
  return i1.start - i2.start;
 }
}
 
public class Solution {
 public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
 
  if (intervals == null || intervals.size() <= 1)
   return intervals;
 
  // sort intervals by using self-defined Comparator
  Collections.sort(intervals, new IntervalComparator());
 
  ArrayList<Interval> result = new ArrayList<Interval>();
 
  Interval prev = intervals.get(0);
  for (int i = 1; i < intervals.size(); i++) {
   Interval curr = intervals.get(i);
 
   if (prev.end >= curr.start) {
    // merged case
    Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end));
    prev = merged;
   } else {
    result.add(prev);
    prev = curr;
   }
  }
 
  result.add(prev);
 
  return result;
 }
}

Time complexity - O(n log n) + O(n) = O(n log n)