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.

Input: [[1,3],[2,6],[8,10],[15,18]]  -> [[1,6],[8,10],[15,18]]
Input: [[1,4],[4,5]]                 -> [[1,5]]
Input: [[1,4],[2,3]]                 -> [[1,4]]

Solution

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 [1,10] with [2,5] must keep the end at 10, not shrink it to 5 - so you take the larger of the two ends rather than blindly using end. Trace [[1,3],[2,6],[8,10],[15,18]] (already start-sorted): [1,3] seeds; [2,6] overlaps since 2 <= 3 so end becomes max(3,6)=6, giving [1,6]; [8,10] has 8 > 6, append; [15,18] has 15 > 10, append. Result [[1,6],[8,10],[15,18]].

Edge cases: touching intervals like [1,4] and [4,5] 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.