# Merge Overlapping Intervals Implement `merge_intervals(intervals)` for a list of closed integer intervals. Each interval is `[start, end]` with `start <= end`. Return the union as non-overlapping intervals sorted by increasing start. Two intervals overlap when they share at least one point. Because the intervals are closed, `[1, 4]` and `[4, 6]` must merge into `[1, 6]`. The input may be unsorted and may contain duplicates or intervals fully contained in other intervals. Do not mutate the caller's list. ## Constraints - `0 <= len(intervals) <= 100000` - `-10^9 <= start <= end <= 10^9` - The output must be deterministic and contain no mergeable adjacent pair. ## Examples - `[[1, 3], [2, 6], [8, 10], [15, 18]]` returns `[[1, 6], [8, 10], [15, 18]]`. - `[[4, 6], [1, 4], [2, 3]]` returns `[[1, 6]]`. - `[]` returns `[]`. ## Clarifications Explain the ordering invariant your implementation relies on, why a single comparison is sufficient after that invariant is established, and the time and auxiliary-space costs. ## Hints Look for an ordering that makes every possible merge partner local rather than requiring all-pairs comparisons. ## Extensions - How would the rule change for half-open intervals `[start, end)`? - How would you merge an incoming interval into an already sorted, non-overlapping list? - What would you change if the input were too large to fit in memory?