⚡Flashcard Drill➔
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

  1. Sort by start ascending, and for equal starts by end descending, so that among equal starts the longest comes first.
  2. Scan while tracking max_end, the largest end seen so far.
  3. An interval is kept only when its end exceeds max_end; otherwise it is covered by an earlier one.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Intervals Problems