Remove Covered Intervals
Problem Statement
You are given an array intervals where intervals[i] = [li, ri]. An interval [a, b] is covered by another interval [c, d] if c <= a and b <= d. Remove every covered interval and return the number of intervals that remain.
Input
An integer matrix intervals, where each row gives the start and end of one interval.
Output
An integer: the number of intervals not covered by any other interval.
Constraints
- •
1 <= intervals.length <= 1000 - •
intervals[i].length == 2 - •
0 <= li < ri <= 10^5 - •
All intervals are unique
Examples
Example 1
intervals = [[1,4],[3,6],[2,8]]
2Example 2
intervals = [[1,4],[2,3]]
1Example 3
intervals = [[0,10],[5,12]]
2Learning Objectives
- Distinguish full containment from ordinary overlap.
- Sort equal-start intervals by descending end to reveal covered intervals correctly.
- Track the farthest end seen so far during a left-to-right sweep.
- Explain why a single maximum end is enough once starts are sorted.
Intuition
Pattern Recognition
The signal is covered, contains, or remove intervals inside other intervals. The trap is treating this like merge intervals. Overlap is not enough; [0,10] and [5,12] overlap but neither covers the other. We need to know whether a previous interval starts no later and ends no earlier.
Sorting by start ascending gives the first half of coverage for free: every previous interval starts at or before the current one. For equal starts, the longer interval must come first; otherwise [1,3] would be counted before [1,4] reveals that it is covered. After that ordering, the only state we need is the largest end seen so far.
Why greedy works / proof sketch
When the sweep reaches an interval [s,e], every earlier interval has start <= s because of the sort. If the largest previous end prevEnd is at least e, then some earlier interval starts no later and ends no earlier, so [s,e] is definitely covered and can be discarded. If e > prevEnd, no earlier interval can cover it because all earlier ends are smaller than e. Keeping it and updating prevEnd is forced. The equal-start descending tie-break makes the strongest covering candidate appear before the intervals it covers.
Common mistakes
- ×Sorting equal starts by end ascending, which counts a shorter interval before the longer interval that covers it.
- ×Checking only whether intervals overlap instead of whether one fully contains the other.
- ×Resetting the tracked end when a covered interval appears; the farthest previous end must stay alive.
- ×Returning the number removed instead of the number remaining.
Algorithm Explanation
Key idea
Sort by start ascending, and when two intervals have the same start, sort by end descending. Sweep once while tracking prevEnd, the farthest end among intervals kept or seen so far. If the current end is less than or equal to prevEnd, the current interval is covered. If it extends beyond prevEnd, it cannot be covered by any earlier interval, so count it as remaining and update prevEnd.
Interval walkthrough
Use intervals = [[1,4],[1,3],[2,8],[3,6]]. After sorting, the number line order is [1,4], [1,3], [2,8], [3,6] because the same-start interval with end 4 comes before end 3. Draw [1,4] as 1 ---- 4 and [1,3] inside it as 1 -- 3; since the farthest end is 4, [1,3] is covered. Then [2,8] stretches beyond the current farthest end, so it remains and moves the boundary to 8. Finally [3,6] sits under 2 ---- 8, so it is covered. Two intervals remain.
Algorithm
- Sort intervals by start ascending.
- For equal starts, sort by end descending so the covering interval is seen first.
- Initialise remaining = 0 and prevEnd to the smallest integer value.
- For each interval [start,end] in sorted order, compare end with prevEnd.
- If end <= prevEnd, the interval is covered, so skip it.
- Otherwise, increment remaining and set prevEnd = end.
- Return remaining.
Solutions
Solution: Sorted containment sweep
Use this when intervals can be sorted and the question asks how many intervals survive full coverage by another interval.
Sort by start ascending and end descending on ties. Then every previous interval starts no later than the current one, so coverage is determined only by whether the current end is within the farthest previous end.
Step-by-step
- Sort intervals by start ascending.
- For equal starts, put the longer interval first by sorting end descending.
- Keep farthestEnd, the largest end among intervals that could cover future intervals.
- If the current end is less than or equal to farthestEnd, skip it as covered.
- Otherwise count it as remaining and update farthestEnd.
- Return the remaining count.
O(n log n)
O(n)
Sorting dominates the sweep. The scan stores only counters, while Java object-array sorting may allocate temporary storage.
Java implementation
Dry Run
Sample input
intervals = [[1,4],[1,3],[2,8],[3,6]]. Sorted order is [[1,4],[1,3],[2,8],[3,6]] because equal starts place the longer interval first.
| sorted interval | farthest end before | covered? | action | remaining |
|---|---|---|---|---|
| [1,4] | none | no | count it and set farthest end to 4 | 1 |
| [1,3] | 4 | yes, 3 <= 4 | skip as covered | 1 |
| [2,8] | 4 | no | count it and extend farthest end to 8 | 2 |
| [3,6] | 8 | yes, 6 <= 8 | skip as covered | 2 |
The remaining intervals are [1,4] and [2,8]. The sweep never needs to remember every previous interval; the maximum end captures the strongest covering candidate.
Interview Tips
Emphasise the difference between overlap and containment. The tie-break is usually where candidates lose points: same start must sort by end descending, otherwise a covered short interval can be counted before its covering long interval. During the sweep, say that prevEnd represents the best covering reach among all earlier starts.
Likely follow-ups
- How would you return the intervals that remain instead of only their count?
- How would the condition change if intervals were open at the right endpoint?
- How would you count intervals covered by at least two other intervals?
- Can you adapt the sweep if intervals arrive already sorted by start but not by equal-start end order?
Similar Problems
Key Takeaways
- Covered intervals require full containment, not just an overlap.
- Sort equal starts by descending end so longer intervals can cover shorter ones immediately.
- After sorting by start, **end <= prevEnd** is exactly the covered condition.
- Counting survivors is easier than physically removing intervals from the array.