Intervals

Intervals are calendar blocks, each with a start and an end. Line them up by start time and walk left to right, gluing together any block that begins before the previous one finishes. Sorting first is the whole trick - it turns 'do any of these overlap?' into one quick neighbour comparison.

Example: [1, 3], [2, 6], [8, 10]. Sorted by start, compare [1, 3] with [2, 6]: since 2 is not after 3, they overlap, so merge them into [1, 6]. Then [8, 10] starts after 6, so it stands on its own. The result is [1, 6] and [8, 10] - cleanly merged in a single pass.

An interval is a pair [start, end]. The single fact everything depends on:

Once you sort by start, you only ever compare the next interval's start to the current merged interval's end — the overlap test simplifies to next.start <= current.end.

Sort by start. Keep a merged list; for each interval, if it overlaps the last merged interval (its start ≤ last end), extend that interval's end to the max of the two; otherwise append it as a new block. One pass after the sort.

Given a sorted, non-overlapping list and a new interval, you can do it in O(n) without re-sorting: copy all intervals that end before the new one starts (no overlap, on the left), then merge the new interval with every interval it overlaps (extending its bounds), then copy the rest (on the right). Three clean phases.

'Minimum meeting rooms' = the maximum number of intervals overlapping at any instant. Two clean approaches: (1) a min-heap of end times — for each meeting sorted by start, pop any room whose meeting has ended, then push this meeting's end; the heap's peak size is the answer. (2) the event/sweep-line: split each interval into a +1 at start and −1 at end, sort all events, and track the running sum's maximum.