Merge overlapping time ranges

← Problems22. Merge overlapping time rangesMediumPython

00:00 / 20:00

Medium100% solve itAsked at Uber, Google

Collapse per-user access windows into the smallest set of non-overlapping ranges. Ranges that touch at the boundary merge.

solve(ranges: list[tuple[int, int, int]]) -> list[tuple[int, int, int]] each tuple is (user_id, start_epoch, end_epoch)

Output sorted by user_id, then start_epoch
Zero-length ranges are valid and must survive if they do not fall inside another range
Input is not sorted
Up to 2,000,000 ranges, so an O(n²) sweep will time out

Input · ranges

[[1, 0, 10], [1, 10, 20], [1, 40, 50], [2, 5, 7]]

Output

[[1, 0, 20], [1, 40, 50], [2, 5, 7]]

Input · ranges

[[1, 40, 50], [1, 0, 10], [1, 5, 20]]

Output

[[1, 0, 20], [1, 40, 50]]

aggregation