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 <= 1000
intervals[i].length == 2
0 <= 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; } }
-
// 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; } };
-
# 1288. Remove Covered Intervals # https://leetcode.com/problems/remove-covered-intervals/ class Solution: def removeCoveredIntervals(self, intervals: List[List[int]]) -> int: n = len(intervals) res = 0 for i in range(n): a,b = intervals[i] check = True for j in range(n): if i != j: c,d = intervals[j] if c <= a and b <= d: check = False break if check: res += 1 return res def removeCoveredIntervals(self, intervals: List[List[int]]) -> int: res = right = 0 intervals.sort(key = lambda x:(x[0],-x[1])) for start,end in intervals: res += end > right right = max(right, end) return res