Merge Intervals — Remove Covered Intervals
↗ LeetCode: Remove Covered Intervals · Medium · pattern chapter →
Asked atAmazonGoogle
Count intervals remaining after removing every interval covered by another.
Example 1 — intervals=[[1,4],[3,6],[2,8]] → 2 (only [3,6] is covered by [2,8]) Example 2 — intervals=[[1,4],[2,3]] → 1
Constraints — 1 ≤ intervals.length ≤ 1000. Brute checks every pair (i, j) for coverage — O(n²) = 10⁸ ops at n=10⁴. Sort by start ascending, end descending → linear pass with running-max-end is O(n log n) = ~10⁵ ops.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — All pairs
O(n²). Baseline.
Approach 2 — Sort by start ascending, end descending; walk (canonical)
Insight. Sort by start asc, break ties by end desc (so the longest-covering interval comes first when starts tie). Walk; track maxEnd. An interval is covered iff its end ≤ maxEnd. Count uncovered.
java
int removeCoveredIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
int count = 0, maxEnd = 0;
for (int[] iv : intervals)
if (iv[1] > maxEnd) { count++; maxEnd = iv[1]; }
return count;
}Execution Trace
Step 1 / 3keep
Complexity — Time O(n log n); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Pairs | O(n²) | O(1) | baseline |
| Sort + walk | O(n log n) | O(1) | optimum |
When to use which
- Sort tie-break matters: same-start intervals — longer must come first.
- "Count covered instead" → total − remaining.
- "Which intervals covered" → track indices before sort, mark during walk.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems