Problem

Given an array intervals where intervals[i] = [li, ri] represent the interval [li, ri), remove all intervals that are covered by another interval in the list.

The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.

Return the number of remaining intervals.

Examples

Example 1:

1
2
3
4
5

Input:
intervals = [[1,4],[3,6],[2,8]]
Output:
 2
Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.

Example 2:

1
2
3
4

Input:
intervals =[[1,4],[2,3]]
Output:
 1

Solution

Method 1 - Sorting

We can sort the intervals:

  • by start time
  • And then by length of interval (in case start times match)

So, now we pick up the interval which are longer; smaller intervals will be ignored or removed. Algo:

  • Sort the array,
  • and note the previous left and right bound.
  • For evert interval v, if v[0] > left && v[1] > right, It’s a new uncovered interval,so we increment ++res.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int removeCoveredIntervals(int[][] intervals) {
	Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);

	int removed = 0, lastEnd = -1;
	for (int[] currInterval : intervals) {

		int currEnd = currInterval[1];
		if (currEnd <= lastEnd) {
			removed += 1;
		} else {
			lastEnd = currEnd;
		}
	}
	return intervals.length - removed;
}