Welcome to Subscribe On Youtube
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.
-
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; } } ############ class Solution { public int removeCoveredIntervals(int[][] intervals) { Arrays.sort(intervals, (a, b) -> a[0] - b[0] == 0 ? b[1] - a[1] : a[0] - b[0]); int[] pre = intervals[0]; int cnt = 1; for (int i = 1; i < intervals.length; ++i) { if (pre[1] < intervals[i][1]) { ++cnt; pre = intervals[i]; } } return cnt; } }
-
// 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; } };
-
class Solution: def removeCoveredIntervals(self, intervals: List[List[int]]) -> int: intervals.sort(key=lambda x: (x[0], -x[1])) cnt, pre = 1, intervals[0] for e in intervals[1:]: if pre[1] < e[1]: cnt += 1 pre = e return cnt ############ # 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
-
func removeCoveredIntervals(intervals [][]int) int { sort.Slice(intervals, func(i, j int) bool { if intervals[i][0] == intervals[j][0] { return intervals[j][1] < intervals[i][1] } return intervals[i][0] < intervals[j][0] }) cnt := 1 pre := intervals[0] for i := 1; i < len(intervals); i++ { if pre[1] < intervals[i][1] { cnt++ pre = intervals[i] } } return cnt }