Merge Intervals Pattern: Meeting Rooms, Insert Interval and More

You stop sorting by start times and start checking end times, which is why your interval code keeps failing on tests. A sorting key that puts the earliest start time first makes every meeting room and railway platform problem linear instead of an accidental quadratic mess.

The Sort Key Mechanics

Take the standard interval array [[1, 3], [2, 6], [8, 10], [15, 18]]. When you sort this array using a custom comparator on the first element, every interval lines up from left to right on the number line.

Intervals.sort(key=lambda x: x[0])

That single line reduces the problem from checking every pair of intervals against every other pair, which takes $O(n^2)$ time, down to an $O(n \log n)$ scan. Once the start times are in order, you only need to compare the end time of the current interval with the start time of the next interval.

Merging and Inserting

In Merge Intervals, you maintain a result list and look at the last added interval to decide whether to combine or append. If the incoming start time is less than or equal to the previous end time, you update the previous end time to the maximum of both end values.

Insert Interval uses the exact same logic, but you drop a new interval like [2, 5] into an already sorted list before you begin the sweep. You skip everything that ends before 2 starts, merge everything that overlaps, and append the rest. The sort key is what lets you skip binary searches and just walk down the array in a single pass.

Meeting Rooms and Minimum Platforms

Resource allocation problems like Meeting Rooms II or Minimum Platforms require a slight shift in the sweep technique. Instead of merging overlapping blocks into one, you count how many intervals overlap at any single coordinate on the number line.

Imagine train arrival times [900, 940, 950, 1100, 1500, 1800] and departure times [910, 1200, 1120, 1130, 1900, 2000]. If you sort arrivals and departures into two separate arrays, you can track concurrency with two pointers. When an arrival time is less than or equal to the departure time, you need a new platform and increment your counter. When a departure happens first, you decrement the counter because a platform just freed up.

A Hand-Worked Trace

Consider the array [[1, 4], [2, 5], [7, 9]].

1. Sort by start times, yielding [[1, 4], [2, 5], [7, 9]].
2. Push [1, 4] to your merged stack.
3. Look at [2, 5]. Its start 2 is less than or equal to the stack top end 4.
4. Update the stack top end to max(4, 5), making it [1, 5].
5. Look at [7, 9]. Its start 7 is strictly greater than 5, so no overlap exists.
6. Push [7, 9] to the stack.
7. The final output is [[1, 5], [7, 9]].

The Rule of Thumb

Sort by start time.
Compare current start with previous end.
Merge on overlap, advance pointer on gap.
Split start and end arrays for resource counting.

Practice Strategy

Open DSA Tracker and filter specifically for interval problems today to lock in this pattern before your next technical round.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Binary search on Wikipedia.