Problem
You are given an array of intervals, whereintervals[i] = [start, end] represents the start and end time of an interval.
Return the minimum number of intervals to remove so that the remaining intervals are non-overlapping.
Intervals that only touch at their endpoints are considered non-overlapping.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
intervals = [[1,2],[2,3],[3,4],[1,3]]Output
1Solution
This problem can be solved using a Greedy Approach.We first sort the intervals by their end time. This is important because when two intervals overlap, we want to keep the interval that finishes earlier. Keeping the interval with the smaller end time leaves more room for the remaining intervals.
We maintain the end time of the last interval we kept. For every next interval, if its start time is less than the current end time, the two intervals overlap.
When an overlap occurs, we remove one of the two intervals. We keep the interval that ends earlier because it gives us the best chance of avoiding future overlaps.
Since the intervals are already sorted by end time, the current interval automatically has the smaller end time, so we simply count the previous interval as removed and update the end time to the current interval's end.
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
// Sort intervals by end time.
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
int removals = 0;
int end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
// Current interval overlaps with the last kept interval.
if (intervals[i][0] < end) {
removals++;
} else {
// Keep the current interval.
end = intervals[i][1];
}
}
return removals;
}
}
Complexity
Sorting the intervals takesO(n log n) time, and traversing the intervals takes O(n) time, resulting in O(n log n) overall time complexity.
Apart from the space used internally by sorting, only a constant number of variables is used, resulting in
O(1) extra space.