Collapse per-user access windows into the smallest set of non-overlapping ranges. Ranges that touch at the boundary merge.
Input schema
solve(ranges: list[tuple[int, int, int]]) -> list[tuple[int, int, int]]
each tuple is (user_id, start_epoch, end_epoch)
Example
Input [(1, 0, 10), (1, 10, 20), (1, 40, 50), (2, 5, 7)]
Output [(1, 0, 20), (1, 40, 50), (2, 5, 7)]
Constraints
- 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
Community-reported interview topic. Not an official company question and no affiliation is implied.