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
- For each interval, compare it with the removed interval
[lo, hi]. - If it lies entirely outside -- it ends at or before
lo, or starts at or afterhi-- keep it unchanged. - Otherwise it overlaps; keep the part before
lo(if the interval starts earlier) and the part afterhi(if it ends later). - 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
loor starting exactly athiis unaffected, so the tests are<=and>=. - Emitting zero-length remainders: the guards
s < loande > hiprevent 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.