Each intervals[i] = [startᵢ, endᵢ] covers every point from startᵢ to endᵢ, both ends included. Combine every group of intervals that overlap — or just touch — into one, and return the result sorted by start.
[1,3] and [2,4] overlap and become [1,4]; [5,7] and [6,9] become [5,9]; [11,11] touches nothing and stays.
They share the point 5, which is enough to merge.
Constraints
1 <= intervals.length <= 10⁴intervals[i].length == 20 <= startᵢ <= endᵢ <= 10⁴Sort the intervals by their start.
Lay the intervals out on a number line. A merged group is a stretch of the line that's covered with no gap, and every interval inside it shares a point with at least one other interval of the group. The answer is those stretches, left to right.
Time O(n log n)Space O(n)
The full walkthrough and code are part of Premium