Merge Intervals

Problem

A calendar service receives booking events from multiple sources, often with overlapping time windows. Storing redundant overlapping intervals wastes space and complicates queries. Given a list of intervals representing bookings, merge all overlapping intervals and return the compacted list.

Example 1:

Input: [[2,5],[3,9],[12,15],[18,22]]
Output: [[2,9],[12,15],[18,22]]
Explanation: [2,5] and [3,9] overlap and merge into [2,9].

Example 2:

Input: [[2,7],[7,9]]
Output: [[2,9]]
Explanation: Touching boundaries [2,7] and [7,9] are considered overlapping.

Example 3:

Input: [[2,8],[3,4]]
Output: [[2,8]]
Explanation: [3,4] is contained inside [2,8], so the outer interval does not shrink.

Constraints:

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start <= end <= 10^4

Solution Breakdown

Approach: sort by start time, then a single left-to-right merge against the last kept interval.

Sorting by start is what makes a one-pass merge correct: once intervals are in non-decreasing start order, any interval that overlaps the current one must be adjacent to it in the sorted list, so you never have to look further back than merged[-1]. Seed merged with the first interval, then for each subsequent [start, end] compare start to merged[-1][1], the end of the last interval you committed. If start <= last_end the two overlap (or touch), so you grow the existing interval in place with merged[-1][1] = max(merged[-1][1], end). Otherwise there is a clean gap, so the current interval starts a new group via merged.append([start, end]).

The max is the subtle part. A later interval can be fully swallowed by the one before it - merging [3,10] with [4,6] must keep the end at 10, not shrink it to 6 - so you take the larger of the two ends rather than blindly using end. Trace [[2,5],[3,9],[12,15],[18,22]] (already start-sorted): [2,5] seeds; [3,9] overlaps since 3 <= 5 so end becomes max(5,9)=9, giving [2,9]; [12,15] has 12 > 9, append; [18,22] has 18 > 15, append. Result [[2,9],[12,15],[18,22]].

Edge cases: touching intervals like [2,7] and [7,9] merge because the condition is <=; a fully contained interval does not shrink its container thanks to the max; unsorted input is handled by the initial sort.

Complexity: O(n log n) time dominated by the sort, O(n) scan; O(n) space for the output list.