Remove Covered Intervals

Problem#

Return the number of intervals that remain after removing every interval covered by some other interval.

Examples#

[[1,4],[3,6],[2,8]] → 2 (drop [3,6])

Constraints#

1 <= intervals.length <= 1000.

Approach#

Sort by start ascending, with end descending as the tiebreaker. Then a single pass: an interval is not covered iff its end exceeds the max end seen so far. The tiebreaker ensures that when two intervals share the start, the longer comes first — making the shorter automatically detect as covered.

Solution#

class Solution {
public:
    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 kept = 0, maxEnd = 0;
        for (auto& it : intervals) {
            if (it[1] > maxEnd) { ++kept; maxEnd = it[1]; }
        }
        return kept;
    }
};

func removeCoveredIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        if intervals[i][0] != intervals[j][0] {
            return intervals[i][0] < intervals[j][0]
        }
        return intervals[i][1] > intervals[j][1]
    })
    kept, maxEnd := 0, 0
    for _, it := range intervals {
        if it[1] > maxEnd {
            kept++
            maxEnd = it[1]
        }
    }
    return kept
}

from typing import List

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[0], -x[1]))
        kept, max_end = 0, 0
        for _, end in intervals:
            if end > max_end:
                kept += 1
                max_end = end
        return kept

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

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        int kept = 0, maxEnd = 0;
        for (int[] it : intervals) {
            if (it[1] > maxEnd) {
                kept++;
                maxEnd = it[1];
            }
        }
        return kept;
    }
}

function removeCoveredIntervals(intervals: number[][]): number {
    intervals.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]);
    let kept = 0;
    let maxEnd = 0;
    for (const it of intervals) {
        if (it[1] > maxEnd) {
            kept++;
            maxEnd = it[1];
        }
    }
    return kept;
}

Editorial#

The combined sort order is the trick. With start ascending, all later intervals have start ≥ current. With end descending on ties, equal starts put the longest interval first; equal-start intervals after it are necessarily covered. So checking “does my end extend the running max?” suffices.

Complexity#

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

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#