How do you solve Remove Covered Intervals?

Sort intervals by start ascending and end descending. Initialize a counter for remaining intervals and a variable to track the maximum end seen. Iterate through intervals; if the current interval's end is greater than the maximum end, increment the counter and update the maximum end. Return the counter as the number of remaining intervals.

Remove Covered Intervals

Q: What is the time complexity of Remove Covered Intervals?

O(n log n). Sorting the intervals takes O(n log n) time. The subsequent single pass through the sorted list is O(n), so the overall time complexity is dominated by sorting.

Q: What pattern does Remove Covered Intervals use?

The Pattern: Greedy Algorithms (Interval Coverage via Sorting) The Heuristic: Sorting intervals by start ascending and end descending arranges intervals so that any covered interval follows its covering interval, enabling a single pass to identify and discard covered intervals by tracking the maximum end boundary.

Medium Greedy Algorithms

Problem

Given a list of intervals, return the number of intervals remaining after removing all intervals that are covered by another interval in the list. An interval [a,b) is covered by [c,d) if and only if c <= a and b <= d.

1 ≤ intervals.length ≤ 1000
intervals[i].length == 2
0 ≤ start_i < end_i ≤ 10⁵

Example

Input: intervals = [[1,4],[3,6],[2,8]]

Output: 2

First, sort intervals by start ascending and end descending: [[1,4],[2,8],[3,6]]. The interval [3,6] is covered by [2,8] because 2 <= 3 and 6 <= 8, so it is removed. The remaining intervals are [1,4] and [2,8], so the output is 2.

Approach

Straightforward Solution

A brute-force approach compares every interval against every other interval to check coverage, resulting in O(n^2) time complexity, which is inefficient for large inputs.

Core Observation

An interval is covered if there exists another interval that starts at or before it and ends at or after it. Sorting intervals by start ascending and end descending ensures that any covered interval appears after its covering interval.

Path to Optimal

Preview

By sorting intervals by start ascending and end descending, the algorithm can scan once, tracking the maximum end seen so far. If the current interval's end is less than or equal to the maximum end, it is covered and skipped…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Sort intervals by start ascending and end descending. Initialize a counter for remaining intervals and a variable to track the maximum end seen…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n log n)

Sorting the intervals takes O(n log n) time. The subsequent single pass through the sorted list is O(n), so the overall time complexity is dominated by sorting.

Space

O(1)

The algorithm uses a constant amount of extra space for counters and variables, modifying the input list in place for sorting.

Pattern Spotlight

Greedy Algorithms (Interval Coverage via Sorting)

Sorting intervals by start ascending and end descending arranges intervals so that any covered interval follows its covering interval, enabling a single pass to identify and discard covered intervals by tracking the maximum end boundary.

Solution

Python

1class Solution:
2    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
3
4        intervals.sort(key=lambda x: (x[0], -x[1]))
5
6        remaining = 0
7        max_end = 0
8
9        for start, end in intervals:
10            if end > max_end:
11                remaining += 1
12                max_end = end
13
14        return remaining

Step-by-Step Solution

Sort Intervals by Start Ascending and End Descending

4	`intervals.sort(key=lambda x: (x[0], -x[1]))`

Objective

To arrange intervals so that potential covering intervals come before covered intervals.

Key Insight

Sorting by start ascending ensures intervals are processed in order of their start points. Sorting by end descending for intervals with the same start places longer intervals first, guaranteeing that any interval that could cover another appears before it. This ordering is critical to enable a single linear scan to detect coverage efficiently.

Interview Quick-Check

Core Logic

Sorting intervals by (start ascending, end descending) arranges intervals so that any covering interval precedes the intervals it covers.

Common Pitfalls & Bugs

Sorting by end ascending instead of descending would place shorter intervals first, breaking the coverage detection logic.

Scan Intervals to Count Non-Covered Ones by Tracking Maximum End

To iterate through sorted intervals and count those not covered by previously seen intervals.

Return the Count of Remaining Intervals

To output the final number of intervals that are not covered by any other interval.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 10 Critical

if end > max_end:

Check if current interval's end is greater than max_end.

If the current interval extends beyond the maximum end seen, it cannot be covered by any previous interval and must be counted.

Line 4 Critical

intervals.sort(key=lambda x: (x[0], -x[1]))

Sort intervals by start ascending and end descending.

This sorting order ensures that intervals that could cover others appear first, enabling a single pass to detect coverage by comparing ends.

Line 12 Critical

max_end = end

Update max_end to current interval's end.

Updating max_end ensures that coverage detection for subsequent intervals is accurate, reflecting the furthest reach of intervals seen so far.

Full line-by-line criticality + rationale for all 8 lines available on Pro.

Test Your Understanding

Why does sorting intervals by start ascending and end descending guarantee that covered intervals appear after their covering intervals?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Remove Covered Intervals from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Remove Covered Intervals drill

or drill a free problem

1	`class Solution:`
2	`def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:`
3
4	`intervals.sort(key=lambda x: (x[0], -x[1]))`
5
6	`remaining = 0`
7	`max_end = 0`
8
9	`for start, end in intervals:`
10	`if end > max_end:`
11	`remaining += 1`
12	`max_end = end`
13
14	`return remaining`