⚡Flashcard Drill➔
NeetCode #830LC-1272MediumIntervalsNC Algo100
← Back to All Problems

#830 · #1272 · Remove Interval(删除区间)

📌 Problem Statement & Constraints

You are given a sorted list of disjoint intervals intervals and an interval toBeRemoved. Return the list of intervals after removing toBeRemoved (the removed part may split an interval in two). Constraints: 1 <= intervals.length <= 10^4, -10^9 <= intervals[i][0] <= intervals[i][1] <= 10^9, sorted and disjoint.

💡 Core Algorithmic Approaches

  1. For each interval, compare it with the removed interval [lo, hi].
  2. If it lies entirely outside -- it ends at or before lo, or starts at or after hi -- keep it unchanged.
  3. Otherwise it overlaps; keep the part before lo (if the interval starts earlier) and the part after hi (if it ends later).
  4. Because the input is sorted and disjoint, each interval contributes at most two pieces and no cross-interval merging is needed.

💻 Benchmark Python3 Implementation

class Solution:
    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[List[int]]) -> List[List[int]]:
        lo, hi = toBeRemoved
        res = []
        for s, e in intervals:
            if e <= lo or s >= hi:              # no overlap
                res.append([s, e])
                continue
            if s < lo:                          # keep the left remainder
                res.append([s, lo])
            if e > hi:                          # keep the right remainder
                res.append([hi, e])
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass over the intervals.
💾 Space Complexity
O(n) for the output.

⚠️ Interview Pitfalls & Follow-ups

  • Using strict inequalities for the no-overlap test: an interval ending exactly at lo or starting exactly at hi is unaffected, so the tests are <= and >=.
  • Emitting zero-length remainders: the guards s < lo and e > hi prevent pieces like [lo, lo].
  • Merging the two remainders: they are separated by the removed interval, so they must stay as two distinct entries.
  • Assuming the removed interval splits at most one interval: it can overlap many, and the per-interval logic handles all of them.
⚡
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