Merge Overlapping Feature Flag Rollout Windows

Problem Statement

A feature-flag platform schedules rollout windows. Each window is [start, end] (timestamps) during which a flag is active. Overlapping or touching windows should be merged into single continuous windows to compute true uptime.

Given a list of rollout windows, return the merged list of non-overlapping windows.

Constraints

• 1 <= windows.length <= 10^5
• 0 <= start <= end <= 10^9
• Windows may be given in any order
• Touching windows ([1,3] and [3,5]) should merge into [1,5]

Example

Input: windows = [[1,3], [2,6], [8,10], [15,18]]

Output: [[1,6], [8,10], [15,18]]

Explanation: [1,3] and [2,6] overlap → merge to [1,6]. The rest don't overlap.

The Insight — Sort by Start, Then Sweep

The whole problem collapses once you realize: sort by start time first, and overlaps can only happen with the interval you just added.

Algorithm:

1. Sort windows by start.
2. Walk through them, keeping a "current" merged window.
3. If the next window's start <= current.end, they overlap → extend current.end = max(current.end, next.end).
4. Otherwise, the current window is finalized → push it, start a new current window.

The "aha": after sorting by start, you never need to look backward — any overlap must involve the most recently merged window. That reduces an O(n²) pairwise-comparison problem to O(n log n) (dominated by the sort).

sort(windows by start)
merged = [windows[0]]
for w in windows[1:]:
    if w.start <= merged[-1].end:
        merged[-1].end = max(merged[-1].end, w.end)
    else:
        merged.append(w)

Follow-ups

1. Why is sorting by start (not end) the right choice here?
2. How would you compute total ACTIVE time (sum of merged window lengths)?
3. What if you needed to INSERT a new window into an already-merged list efficiently?
4. How does this relate to the "meeting rooms" problem (minimum rooms needed)?