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:

1
2

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

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;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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()][]);
}
 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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).