Meteor Windows
Astronomers booked telescope windows as [start, end] pairs, in no particular order. Write merge_windows(windows) that merges every pair of windows that overlap or touch, and returns the merged windows sorted by start time.
For example, [1, 3] and [2, 6] overlap, so they become [1, 6]. [1, 4] and [4, 5] touch, so they become [1, 5]. Aim for O(n log n): sort once, then make a single pass.
Examples
merge_windows([[1, 3], [2, 6], [8, 10], [15, 18]])
→ [[1, 6], [8, 10], [15, 18]]
merge_windows([[1, 4], [4, 5]])
→ [[1, 5]]
solution.py
PYTHON
Saved as you type
Tests
0 of 5 passing- •overlaps mergemerge_windows([[1, 3], [2, 6], [8, 10], [15, 18]])expected [[1, 6], [8, 10], [15, 18]]
- •touching windows mergemerge_windows([[1, 4], [4, 5]])expected [[1, 5]]
- •no windowsmerge_windows([])expected []
- •unsorted inputmerge_windows([[5, 7], [1, 2]])expected [[1, 2], [5, 7]]
- •one window swallows othersmerge_windows([[1, 10], [2, 3], [4, 5]])expected [[1, 10]]
On the line
+80 XP
Pass all 5 tests to claim it.