Remove Covered Intervals

medium intervals sorting

Problem

Given a list of intervals, remove all intervals that are covered by another in the list. An interval [a, b) is covered by [c, d) if c ≤ a and b ≤ d. Return the number of remaining intervals.

Inputintervals = [[1,4],[3,6],[2,8]]

Output2

[3,6] is covered by [2,8]. The survivors are [1,4] and [2,8].

intervals (e.g. [[1,4],[3,6],[2,8]])

def remove_covered_intervals(intervals):
    intervals.sort(key=lambda x: (x[0], -x[1]))
    count = 0
    max_end = 0
    for a, b in intervals:
        if b > max_end:
            count += 1
            max_end = b
    return count

function removeCoveredIntervals(intervals) {
  intervals.sort((a, b) => a[0] - b[0] || b[1] - a[1]);
  let count = 0, maxEnd = 0;
  for (const [a, b] of intervals) {
    if (b > maxEnd) { count++; maxEnd = b; }
  }
  return count;
}

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (x, y) -> x[0] != y[0] ? x[0] - y[0] : y[1] - x[1]);
        int count = 0, maxEnd = 0;
        for (int[] iv : intervals) {
            if (iv[1] > maxEnd) { count++; maxEnd = iv[1]; }
        }
        return count;
    }
}

int removeCoveredIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
        return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];
    });
    int count = 0, maxEnd = 0;
    for (auto& iv : intervals) {
        if (iv[1] > maxEnd) { count++; maxEnd = iv[1]; }
    }
    return count;
}

Explanation

An interval is "covered" when another interval completely swallows it. We want to count how many intervals survive after dropping every covered one. The clever move is a careful sort so a single left-to-right pass can decide coverage.

We sort by start ascending, and break ties by end descending. This ordering guarantees that whenever we reach an interval, any interval that could cover it has already been seen, and the tie-break ensures the wider interval comes first so the narrower equal-start one is recognised as covered.

We keep max_end, the largest end value seen so far. For the current interval [a, b], if b > max_end it extends past everything before it, so it cannot be covered — we count it and update max_end. If b ≤ max_end, some earlier interval already reaches at least as far while starting no later, so this one is covered and skipped.

Example: [[1,4],[3,6],[2,8]] sorts to [1,4], [2,8], [3,6]. Keep [1,4] (max_end=4), keep [2,8] (8 > 4, max_end=8), then [3,6] has 6 ≤ 8 so it is covered. Survivors = 2.

The sort costs O(n log n) and the single sweep is linear, using only a couple of variables.

Time: O(n log n) Space: O(1) extra