Given a list of closed intervals in any order, merge every pair that overlaps or touches, and return the result sorted by start. [1,4] and [4,5] touch, and merge into [1,5].
Examples
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Example 3:
Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]
Explanation: the input is not sorted; the answer still is.
Example 4:
Input: intervals = [[1,4],[2,3]]
Output: [[1,4]]
Constraints
1 <= intervals.length <= 10^4
intervals[i] is [start, end] with 0 <= start <= end <= 10^5
Prerequisites
Sorting as a setup move — most interval problems are one sort away from a single sweep, and choosing whether to sort by START or by END is the decision that matters.
How to think about it
1. Sort by Start, Then Sweep Optimal
Intuition
Sorted by start, an interval can only overlap the one immediately before it in the merged output — so a single sweep decides everything: extend the last merged interval, or begin a new one. Touching counts as overlapping, which is why the comparison is "starts at or before" rather than strictly before.
Algorithm
1. Sort by start. 2. For each interval, if it starts at or before the last merged one's end, raise that end to the larger of the two. 3. Otherwise append it as a new interval.
Time & Space
Time O(n log n), dominated by the sort. Space O(n).