NeetCode #848LC-352HardIntervals
← Back to All Problems#848 · #352 · Data Stream as Disjoint Intervals(将数据流变为多个不相交区间)
📌 Problem Statement & Constraints
Given a data stream of non-negative integers, design a structure that summarises the numbers seen so far as a list of disjoint sorted intervals. Implement
addNum(value) and getIntervals(). Constraints: 0 <= value <= 10^4, at most 3 * 10^4 calls in total.💡 Core Algorithmic Approaches
- Maintain the summary as a list of disjoint intervals sorted by start.
- On
addNum, binary search for the position just after the last interval whose start is at mostvalue. - If the previous interval's end is at least
value - 1, extend it to includevalue; otherwise insert a new singleton interval. - Then repeatedly merge with the following interval while the gap is at most one, keeping the invariant intact.
💻 Benchmark Python3 Implementation
class Solution:
def __init__(self):
self.intervals = [] # sorted disjoint [start, end]
def addNum(self, value: int) -> None:
from bisect import bisect_right
intervals = self.intervals
i = bisect_right(intervals, [value, float("inf")]) # first start > value
if i > 0 and intervals[i - 1][1] >= value - 1:
i -= 1
intervals[i][1] = max(intervals[i][1], value)
else:
intervals.insert(i, [value, value])
while i + 1 < len(intervals) and intervals[i][1] + 1 >= intervals[i + 1][0]:
intervals[i][1] = max(intervals[i][1], intervals[i + 1][1])
intervals.pop(i + 1)
def getIntervals(self) -> List[List[int]]:
return self.intervals⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n) per addNum in the worst case due to the list insertion; the merge itself is amortised O(1) per interval.
💾 Space Complexity
O(n): the interval list.
⚠️ Interview Pitfalls & Follow-ups
- Merging only with the immediate neighbour: adding a value can bridge two intervals at once (for example
[1,2]and[4,5]with3), which the while loop handles. - Using
>= valueinstead of>= value - 1: adjacent intervals merge, so a gap of exactly one must be bridged. - Forgetting the merge with the previous interval: the binary search lands after all intervals with start at most
value, so the previous one may need extending. - Returning internal references:
getIntervalsreturns the live list; callers that mutate it would corrupt the structure, but LeetCode's checker only reads it.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.