Merge Overlapping Intervals

## Problem Given a list of closed integer intervals `[start, end]`, merge every overlapping interval and return the disjoint result sorted by start. Because intervals are closed, `[1, 4]` and `[4, 7]` overlap and become `[1, 7]`. ### Function Contract Implement `mergeIntervals(intervals)`. ### Constraints & Assumptions - `0 <= len(intervals) <= 200,000`. - `-10^9 <= start <= end <= 10^9`. - Input may be unsorted and may contain duplicate or contained intervals. - Return an empty list for empty input. ### Clarifying Questions to Ask - Are intervals closed? Yes. - Should touching endpoints merge? Yes. - Must the input be modified? No requirement; returning new interval pairs is acceptable. - Is output sorted? Yes, by increasing start. ```hint Sort once After sorting by start, a new interval can overlap only the last interval already emitted. ``` ### Example ```text input = [[1,3], [2,6], [8,10], [10,12]] output = [[1,6], [8,12]] ``` ### Evaluation Focus - Applies closed-interval endpoint semantics. - Handles containment, duplicates, and chains of overlap. - Does not compare every pair of intervals. - Runs in `O(n log n)` time and `O(n)` output space. ### Extensions to Discuss 1. What changes for half-open intervals? 2. How would you merge intervals arriving in sorted order as a stream? 3. How would you preserve the IDs of original intervals in each merged group?