Merge Overlapping Time Windows

## Problem Merge a collection of time windows so that the output contains sorted, non-overlapping half-open intervals. A window `[start, end)` includes `start` and excludes `end`; therefore adjacent windows `[1, 3)` and `[3, 5)` do not overlap and remain separate. ### Function Contract Implement `mergeTimeWindows(windows)`. ### Constraints & Assumptions - `0 <= len(windows) <= 200,000`. - `0 <= start < end <= 10^12`. - Windows may be unsorted, duplicated, or nested. - Output uses the same half-open semantics. ### Clarifying Questions to Ask - Do adjacent windows merge? No, only positive-duration overlap merges them. - How should duplicates be handled? One copy remains after merging. - Is stable ordering among identical starts important? No. - Should invalid windows be skipped? No; inputs are valid. ```hint Compare with the last merged end After sorting, overlap exists exactly when the next start is strictly less than the current merged end. ``` ### Example ```text input = [[1,3], [2,6], [8,10], [10,12]] output = [[1,6], [8,10], [10,12]] ``` ### Evaluation Focus - Distinguishes overlap from adjacency under half-open semantics. - Extends the end with `max(currentEnd, nextEnd)` for nested windows. - Produces sorted disjoint output. - Runs in `O(n log n)` time. ### Extensions to Discuss 1. How would the output change under closed-interval semantics? 2. How would you compute the total covered duration? 3. Which structure supports online insertion and coverage queries?