Formatted question description: https://leetcode.ca/all/1288.html
1288. Remove Covered Intervals (Medium)
Given a list of intervals, remove all intervals that are covered by another interval in the list.
Interval [a,b) is covered by interval [c,d) if and only if c <= a and b <= d.
After doing so, return the number of remaining intervals.
Example 1:
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:
Input: intervals = [[1,4],[2,3]] Output: 1
Example 3:
Input: intervals = [[0,10],[5,12]] Output: 2
Example 4:
Input: intervals = [[3,10],[4,10],[5,11]] Output: 2
Example 5:
Input: intervals = [[1,2],[1,4],[3,4]] Output: 1
Constraints:
1 <= intervals.length <= 1000intervals[i].length == 20 <= intervals[i][0] < intervals[i][1] <= 10^5- All the intervals are unique.
Related Topics:
Greedy, Sort, Line Sweep
Solution 1.
// OJ: https://leetcode.com/problems/remove-covered-intervals/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int removeCoveredIntervals(vector<vector<int>>& A) {
sort(begin(A), end(A), [](auto &a, auto &b) { return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1]; });
int ans = A.size(), e = INT_MIN;
for (auto &r : A) {
if (r[1] <= e) --ans;
else e = r[1];
}
return ans;
}
};
Java
class Solution {
public int removeCoveredIntervals(int[][] intervals) {
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(int[] array1, int[] array2) {
if (array1[0] != array2[0])
return array1[0] - array2[0];
else
return array1[1] - array2[1];
}
});
int length = intervals.length;
boolean[] remove = new boolean[length];
for (int i = 0; i < length; i++) {
int[] interval1 = intervals[i];
for (int j = i + 1; j < length; j++) {
int[] interval2 = intervals[j];
if (interval2[1] <= interval1[1])
remove[j] = true;
if (interval2[0] > interval1[1])
break;
}
}
int removeCount = 0;
for (int i = 0; i < length; i++) {
if (remove[i])
removeCount++;
}
return length - removeCount;
}
}