Question

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

Solution 1

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

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;
  }
};

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
}