NeetCode #840LC-1288MediumIntervals
← Back to All Problems#840 · #1288 · Remove Covered Intervals(删除被覆盖区间)
📌 Problem Statement & Constraints
You are given an array of intervals
intervals. Remove all intervals that are covered by another interval (an interval [a, b] is covered by [c, d] if c <= a and b <= d). Return the number of remaining intervals. Constraints: 1 <= intervals.length <= 1000, 0 <= intervals[i][0] <= intervals[i][1] <= 10^5, all intervals are distinct.💡 Core Algorithmic Approaches
- Sort by start ascending, and for equal starts by end descending, so that among equal starts the longest comes first.
- Scan while tracking
max_end, the largest end seen so far. - An interval is kept only when its end exceeds
max_end; otherwise it is covered by an earlier one. - The tie-break on equal starts is essential: it makes the longest interval appear first so the shorter ones are correctly marked as covered.
💻 Benchmark Python3 Implementation
class Solution:
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: (x[0], -x[1])) # start asc, end desc
count = 0
max_end = 0
for _, e in intervals:
if e > max_end: # not covered by anything before it
count += 1
max_end = e
return count⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort dominates.
💾 Space Complexity
O(1) beyond the sort.
⚠️ Interview Pitfalls & Follow-ups
- Sorting by start ascending and end ascending: with equal starts the shorter interval would come first and wrongly survive.
- Using
e >= max_end: an interval with the same end but a later start is covered, so the test is strict>. - Comparing only against the previous interval: coverage can come from any earlier interval, so the running maximum end is required.
- Forgetting that intervals are distinct: the guarantee avoids duplicate-interval ambiguity; with duplicates the count would need care.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.