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 the two intervals have the same `start`, put the one with a larger
    // `end` first.
    ranges::sort(intervals, [](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
19
20
class Solution {
  public int removeCoveredIntervals(int[][] intervals) {
    // If the two intervals have the same `start`, put the one with a larger
    // `end` first.
    Arrays.sort(intervals,
                (a, b) -> a[0] == b[0] ? Integer.compare(b[1], a[1]) : Integer.compare(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
14
class Solution:
  def removeCoveredIntervals(self, intervals: list[list[int]]) -> int:
    ans = 0
    prevEnd = 0

    # If the two intervals have the same `start`, put the one with a 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