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

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?