Remove Covered Intervals

How it works

With a simpler sort by start time only, we track the maximum end point seen so far. An interval is covered if both its start is greater than or equal to a previous start AND its end is within the maximum end we've tracked. By keeping the maximum end updated, we efficiently determine coverage in a single pass.

Steps

1. Sort intervals by start time.
2. Track the start and maximum end of the current "dominant" interval.
3. For each interval, check if it extends beyond the current coverage (new start strictly greater AND new end strictly greater).
4. If so, it's a new uncovered interval. Update the tracked start and increment the count.
5. Always update the maximum end seen.
6. Return the count.

This approach avoids the need for special sorting by end time in reverse.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(1) or O(n) depending on the sorting algorithm.

Things to watch for

Incorrect Sorting Order

The most common mistake is sorting only by start time without considering the end time. When two intervals share the same start, the longer one should come first (sort by end time descending). Otherwise, you might incorrectly count the longer interval as covered by the shorter one. For example, [1,4] and [1,2] with the same start: if [1,2] comes first, you'd miss that [1,2] is covered by [1,4].

Confusing Covered vs Overlapping

An interval is covered only if another interval completely contains it (start <= start AND end >= end). Some solutions incorrectly check for overlap instead of complete containment. For [1,4] to cover [2,3], we need 1 <= 2 AND 4 >= 3. Partial overlaps like [1,3] and [2,4] don't count as one covering the other.

Off-by-One in Return Value

The problem asks for the count of intervals remaining after removal, not the count of covered intervals. Some solutions return the number of covered intervals instead of subtracting from the total. If you find k covered intervals out of n total, return n - k, not k.

from typing import List

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        res, start, end = 1, intervals[0][0], intervals[0][1]

        for l, r in intervals:
            if start < l and end < r:
                start = l
                res += 1
            end = max(end, r)

        return res

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int res = 1, start = intervals[0][0], end = intervals[0][1];

        for (const auto& interval : intervals) {
            int l = interval[0], r = interval[1];
            if (start < l && end < r) {
                start = l;
                res++;
            }
            end = max(end, r);
        }
        return res;
    }
};