Welcome to Subscribe On Youtube

1288. Remove Covered Intervals

Description

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.

 

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

 

Constraints:

  • 1 <= intervals.length <= 1000
  • intervals[i].length == 2
  • 0 <= li < ri <= 105
  • All the given intervals are unique.

Solutions

  • Sort intervals by increasing of startTime and decreasing of endTime.
  • cnt = 1: cnt is the result.
  • pre = intervals[0]: pre is the last interval
  • For each interval in intervals
    • if pre.endTime < interval.endTime, means interval is not overlapped then we count cnt, and update pre = interval
    • else we do nothing
  • Return cnt
  • 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; } } 
  • class Solution { public: int removeCoveredIntervals(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] == b[0] ? b[1] < a[1] : a[0] < b[0]; }); int cnt = 1; vector<int> pre = intervals[0]; for (int i = 1; i < intervals.size(); ++i) { if (pre[1] < intervals[i][1]) { ++cnt; pre = intervals[i]; } } return cnt; } }; 
  • 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 
  • 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 } 
  • function removeCoveredIntervals(intervals: number[][]): number { intervals.sort((a, b) => (a[0] === b[0] ? b[1] - a[1] : a[0] - b[0])); let ans = 0; let pre = -Infinity; for (const [_, cur] of intervals) { if (cur > pre) { ++ans; pre = cur; } } return ans; } 
  • /** * @param {number[][]} intervals * @return {number} */ var removeCoveredIntervals = function (intervals) { intervals.sort((a, b) => (a[0] === b[0] ? b[1] - a[1] : a[0] - b[0])); let ans = 0; let pre = -Infinity; for (const [_, cur] of intervals) { if (cur > pre) { ++ans; pre = cur; } } return ans; };

All Problems

All Solutions