Remove Covered Intervals - Video Solutions

Problem Overview: You are given a list of intervals where each interval is represented as [start, end]. An interval is considered covered if another interval fully contains it. The task is to remove all covered intervals and return the number of remaining intervals.

Approach 1: Graph-Based Comparison (Implicit Graph) (O(n²) time, O(1) extra space)

Treat every interval as a node and check coverage relationships between all pairs. For each interval i, iterate through every other interval j. If j.start ≤ i.start and j.end ≥ i.end, interval i is covered and should not be counted. This brute-force comparison effectively builds an implicit coverage graph without storing edges. The method is straightforward and helps you reason about the definition of coverage, but the nested iteration leads to O(n²) time complexity. Space stays O(1) because only counters and temporary variables are used.

Approach 2: Sort by Start, End Descending (O(n log n) time, O(1) space)

The optimal solution relies on sorting. Sort intervals by start in ascending order. When two intervals share the same start, sort by end in descending order. This ordering guarantees that larger covering intervals appear before the smaller ones they might contain.

After sorting, scan the array once while tracking the maximum end value seen so far. If the current interval's end is less than or equal to that maximum, it is covered by a previous interval. Otherwise, it is a valid interval that should be counted, and the maximum end gets updated. Because sorting groups potential coverings together, a single linear pass is enough to detect coverage relationships.

This approach combines array traversal with sorting order to eliminate the need for pairwise comparisons. Sorting costs O(n log n), and the scan is O(n). No additional data structures are required beyond a few variables, so extra space remains O(1) (ignoring sort implementation details).

Recommended for interviews: The sorting approach is the expected solution. It shows you recognize that ordering intervals can simplify containment checks and reduce the complexity from O(n²) to O(n log n). Explaining the brute-force comparison first demonstrates clear understanding of the coverage rule, while the optimized sorting strategy shows strong algorithmic thinking using sorting and interval scanning patterns.