Intervals — How the Pattern Works
The Intervals pattern processes collections of [start, end] ranges by sorting them by start coordinate (or decomposing ranges into boundary events) and sweeping from left to right in a single pass. Sorting establishes the monotonic invariant intervals[i][0] <= intervals[i + 1][0], guaranteeing that all ranges overlapping the active span appear consecutively and only need comparison against the furthest active end seen so far (or a min-heap of active end times). This eliminates O(n^2) pairwise overlap checks and coordinate-dependent O(T) timeline scans, solving merge, gap, containment, and concurrency problems in O(n log n) time (or O(n) when pre-sorted).
- Input consists of [start, end] pairs representing meetings, schedules, reservations, trips, or numeric ranges.
- Prompt asks to merge overlapping intervals, insert a range into sorted disjoint intervals, or remove covered/nested intervals.
- Prompt asks to find shared intersections, common free time across schedules, or uncovered gaps within a bounded timeline.
- Prompt asks for peak concurrency or resource capacity (minimum meeting rooms, vehicle seat capacity across overlapping trips).
- Prompt asks to answer offline point-containment queries over ranges or maintain disjoint intervals dynamically from an integer stream.
- Comparing the next interval's start against the previous interval's raw end instead of max_end so far — a nested short interval like [2, 3] inside [1, 5] shrinks the tracked boundary and misses subsequent overlaps such as [4, 8].
- Off-by-one boundary semantics when end == next_start: closed-interval merging treats touching endpoints as overlapping (start <= end), whereas room reuse and passenger drop-offs free capacity at end <= start (requiring -delta drop-off events to sort before +delta pickups at identical coordinates).
- Breaking start-time ties in ascending rather than descending end order for containment problems: given [1, 4] and [1, 6], sorting [1, 4] first fails to detect that [1, 6] covers [1, 4]; always sort with key=lambda x: (x[0], -x[1]).
- Allocating timeline arrays of size O(max_end) instead of sweeping sorted interval endpoints in O(n log n), triggering memory or time limit failures when coordinates reach 10^9.
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return mergedimport heapq
def min_resources(intervals):
intervals.sort(key=lambda x: x[0])
ends = []
for start, end in intervals:
if ends and ends[0] <= start:
heapq.heapreplace(ends, end)
else:
heapq.heappush(ends, end)
return len(ends)def within_capacity(trips, capacity):
events = []
for weight, start, end in trips:
events.append((start, weight))
events.append((end, -weight))
load = 0
for _, delta in sorted(events):
load += delta
if load > capacity:
return False
return True