Skip to content

1288. Remove Covered Intervals 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int removeCoveredIntervals(vector<vector<int>>& intervals) {
    // If two intervals have the same start, put the one with larger end first.
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) {
      return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
    });

    int ans = 0;
    int prevEnd = 0;

    for (const vector<int>& interval : intervals)
      // Current interval is not covered by the previous one.
      if (prevEnd < interval[1]) {
        ++ans;
        prevEnd = interval[1];
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int removeCoveredIntervals(int[][] intervals) {
    // If two intervals have the same start, put the one with larger end first.
    Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);

    int ans = 0;
    int prevEnd = 0;

    for (int[] interval : intervals)
      // Current interval is not covered by the previous one.
      if (prevEnd < interval[1]) {
        ++ans;
        prevEnd = interval[1];
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
    ans = 0
    prevEnd = 0

    # If two intervals have the same start, put the one with larger end first.
    for _, end in sorted(intervals, key=lambda x: (x[0], -x[1])):
      # Current interval is not covered by the previous one.
      if prevEnd < end:
        ans += 1
        prevEnd = end

    return ans