Interval Tree / Overlapping Time Range Merger
Consolidating meeting schedules or memory reservations requires merging overlapping ranges. After sorting intervals by start times, interval `[c, d]` overlaps preceding `[a, b]` whenever $c \le b$. The range collapses into `[a, max(b, d)]` in a single linear sweep ⏱️📅⚡.
def merge_ranges(ranges):
ordered = sorted(ranges, key=lambda x: x[0])
merged = [ordered[0]]
for s, e in ordered[1:]:
prev_s, prev_e = merged[-1]
if s <= prev_e: merged[-1] = (prev_s, max(prev_e, e))
else: merged.append((s, e))
return merged
print("Merged:", merge_ranges([(1, 4), (2, 6), (8, 10)]))
# 20. Interval Tree / Overlapping Time Range Merger In calendar applications, disk defragmentation engines, cloud resource reservation managers, and database transaction lock range checks, you constantly deal with overlapping time or byte intervals 🛑. ```python # The Overlap Condition: # Two sorted intervals [s1, e1] and [s2, e2] overlap IF AND ONLY IF: # s2 <= e1 # # When overlapping: # Merged interval = [s1, max(e1, e2)] ``` ### The $O(N \log N)$ Pipeline 1. **Sort by Start Position ($O(N \log N)$)**: This transforms an $O(N^2)$ all-pairs comparison problem into a single sequential scan. 2. **Linear Sweep ($O(N)$)**: Maintain a `merged` list. For each incoming interval `(s, e)`: - If `s <= last_end`: Extend `last_end = max(last_end, e)`. - Else: Append as a distinct non-overlapping interval. - Total Time: **$O(N \log N)$** (sorting dominates). Space: **$O(N)$** ⏱️📅⚡. --- ### Interactive Pop-Quiz 🧠 #### Why is sorting intervals by their start time the critical prerequisite before attempting an $O(N)$ linear merge? - [ ] Sorting ensures that any interval that could possibly overlap with the current range is positioned immediately adjacent to it in the iteration sequence 📅 - [ ] Because Python `max()` requires sorted inputs - [ ] Sorting converts tuples into memory-mapped arrays - [ ] Because unsorted intervals crash the CPU arithmetic logic unit --- ### Practical Challenge 🎯 Implement `merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]`. Sort by start time and merge contiguous and overlapping ranges. Test with `[(1, 3), (2, 6), (8, 10), (15, 18)]` (expect `[(1, 6), (8, 10), (15, 18)]`), and `[(1, 4), (4, 5)]` (expect `[(1, 5)]`). Assert both results and print output. <details> <summary>Solution</summary> ```python def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]: if not intervals: return [] sorted_ivs = sorted(intervals, key=lambda x: x[0]) merged = [sorted_ivs[0]] for start, end in sorted_ivs[1:]: last_start, last_end = merged[-1] if start <= last_end: merged[-1] = (last_start, max(last_end, end)) else: merged.append((start, end)) return merged iv1 = [(1, 3), (2, 6), (8, 10), (15, 18)] iv2 = [(1, 4), (4, 5)] res1 = merge_intervals(iv1) res2 = merge_intervals(iv2) assert res1 == [(1, 6), (8, 10), (15, 18)] assert res2 == [(1, 5)] print(f"Intervals merged successfully: {res1} and {res2}") ``` </details>