#1288

Medium

LeetCode Problem Workspace

Remove Covered Intervals

Remove all intervals fully covered by another using sorting and linear traversal, counting only distinct remaining intervals.

array sorting

Problem Statement

You are given an array of intervals where each interval is represented as [li, ri). An interval [a, b) is considered covered by [c, d) if c <= a and b <= d. Remove all intervals that are covered by another interval in the array.

After removing covered intervals, return the number of intervals that remain. Ensure your solution accounts for overlapping intervals and nested intervals efficiently, using sorting to expose coverage patterns.

Examples

Example 1

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

Output: 2

Interval [3,6] is covered by [2,8], therefore it is removed.

Example 2

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

Output: 1

Example details omitted.

Constraints

1 <= intervals.length <= 1000
intervals[i].length == 2
0 <= li < ri <= 105
All the given intervals are unique.

Solution Approach

Sort Intervals by Start and End

Sort the intervals first by their start in ascending order, and then by their end in descending order. This ensures that longer intervals appear before shorter intervals that start at the same point, exposing potential coverage relationships.

Linear Scan to Remove Covered Intervals

Initialize a variable to track the maximum end seen so far. Traverse the sorted intervals; if the current interval's end is less than or equal to the maximum end, it is covered and skipped. Otherwise, update the maximum end and count it as remaining.

Return Remaining Interval Count

After the linear scan, the remaining intervals are those not fully covered. Return the total count of these intervals, which efficiently handles nested and overlapping cases without extra space for a new array.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting the intervals takes O(n log n), and the linear traversal is O(n), resulting in overall O(n log n) time. Space complexity is O(1) if counting in place, or O(n) if storing non-covered intervals separately.

What Interviewers Usually Probe

Do you notice how sorting by start and reverse end helps reveal coverage?
Can you track the maximum end to avoid checking every pair?
How does your approach scale with 1000 intervals and nested ranges?

Common Pitfalls or Variants

Common pitfalls

Not sorting by end descending, causing smaller intervals to appear before larger ones starting at the same position.
Comparing every interval with all others, leading to O(n^2) inefficiency.
Failing to handle intervals with the same start but different lengths correctly.

Follow-up variants

Return the list of intervals that remain instead of the count.
Handle intervals with inclusive end points instead of half-open intervals.
Detect all intervals fully contained within multiple overlapping intervals.

FAQ

What is the best sorting order for Remove Covered Intervals?

Sort intervals by start ascending and end descending to expose which intervals can cover others in a single linear pass.

Can overlapping intervals affect the count?

Yes, overlapping intervals must be checked carefully; only intervals fully covered by another are removed.

Does this approach work for large arrays up to 1000 intervals?

Yes, sorting plus a single linear scan handles arrays of length up to 1000 efficiently in O(n log n) time.

How do you detect if an interval is covered?

Compare the current interval's end with the maximum end seen so far; if it is less than or equal, it is covered.

Is Remove Covered Intervals always solvable with array and sorting pattern?

Yes, sorting exposes coverage relationships and allows linear scanning, perfectly matching the array plus sorting pattern.

terminal

Solution

Solution 1: Sorting

We can sort the intervals in ascending order by their left endpoints, and if the left endpoints are the same, sort them in descending order by their right endpoints.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#1296 divide array in sets of k consecutive numbers #1300 sum of mutated array closest to target #1268 search suggestions system