Problem

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.

OR

Given a list of intervals, merge all the overlapping intervals to produce a list that has only mutually exclusive intervals.

Examples

Example 1:

Input: intervals = [1,3],[2,6],[8,10],[15,18],
Output: [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 start time.

Lets take 3 intervals in sorted array of intervals as a, b and c as interval[i - 1], interval[i] and interval[i+1].

If interval a doesn’t overlap with interval b, then interval c cannot overlap with interval a, because starting time of c must be greater than or equal to b.

Then, we can combine all sorted intervals in a linear traversal.

Following is the detailed step by step algorithm :

  1. Sort the intervals based on increasing order of start 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

Java
Interval as class

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 List<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());

		List<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); // edge case
		return result;
	}
}
Interval as array

In Leetcode, interval is given as array. So, to avoid conversion from array to interval and vice versa, here is another code:

public int[][] merge(int[][] intervals) {
	//sorted on the basis starting point of intrevals
    Arrays.sort(intervals, (a,b) -> Integer.compare(a[0], b[0]));

	List<int[]> ans = new ArrayList<>();
	int[] prev = intervals[0];
	for(int i = 1; i < intervals.length; i++){ 
		int[] curr = intervals[i];
		// overlap
		if(prev[1] >= curr[0]){
			prev[1] = Math.max(prev[1], curr[1]);
		}else {
			ans.add(prev);
			prev = curr;
		}
	}
	ans.add(prev);//edge case
	return ans.toArray(new int[ans.size()][]);
}

We can avoid the edge case, where prev is not part of the answer yet, by adding it in the start itself:

public List<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());

	List<Interval> result = new ArrayList<Interval> ();
	result.add(intervals.get(0));
	for (int i = 1; i<intervals.size(); i++) {
		Interval curr = intervals.get(i);
		Interval prev = result.get(result.size()-1);
		if (prev.end >= curr.start) {
			// merged case
			Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end));
			result.set(result.size()-1, merged);
		} else {
			result.add(curr);
		}
	}

	return result;
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n) or O(1)

The space complexity of the above algorithm will be O(N) as we need to return a list containing all the merged intervals. We will also need O(N) space for sorting. For Java, depending on its version, Collection.sort() either uses Merge sort or Timsort, and both these algorithms need O(N) space. Overall, our algorithm has a space complexity of O(N).