Breaking Down the Interval Family: Merge Intervals to Meeting Rooms III

Interval problems all start with the same move and then branch based on one question. This post walks the family in the order the follow-ups actually arrive in an interview: Merge Intervals → Insert Interval → Meeting Rooms II, solved three different ways.

56. Merge Intervals

Overlapping intervals could be anywhere in the array — that's the difficulty. Sorting by start collapses it: after sorting, an interval can only overlap its neighbor, so one linear pass finishes the job.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda i: i[0])
 
        merged = [intervals[0]]
 
        for start, end in intervals[1:]:
            lastEnd = merged[-1][1]
 
            if start <= lastEnd:
                merged[-1][1] = max(lastEnd, end)
            else:
                merged.append([start, end])
 
        return merged

Time: O(n log n) / Space: O(n)

Two details carry this problem:

• The invariant: merged stays disjoint and sorted, so merged[-1][1] is always the largest end seen so far. That's why comparing against just one value is sufficient.
• The max(): an interval can sit completely inside the previous one — [1,10],[2,3]. Overwrite the end with end instead of max(lastEnd, end) and the end shrinks from 10 to 3, the invariant breaks, and later intervals get judged against the wrong boundary.

start <= lastEnd — the <= means touching intervals like [1,2],[2,3] merge. Worth confirming with the interviewer; it flips per problem.

57. Insert Interval

The input is already sorted and non-overlapping — one new interval needs to be slotted in. The sorted premise is exactly what removes the O(n log n): no sorting, one pass.

I like writing it in the same shape as Merge Intervals — carry an interval, compare, absorb or place:

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
 
        for i in range(len(intervals)):
            if intervals[i][1] < newInterval[0]:
                # ends before the new one starts — keep as-is
                res.append(intervals[i])
 
            elif intervals[i][0] > newInterval[1]:
                # starts after the new one ends — the new interval
                # can't grow anymore; place it and bail out
                res.append(newInterval)
                return res + intervals[i:]
 
            else:
                # overlap — absorb into the new interval.
                # min AND max: unlike Merge Intervals, this
                # interval grows in BOTH directions
                newInterval = [min(newInterval[0], intervals[i][0]),
                               max(newInterval[1], intervals[i][1])]
 
        # never hit the "completely after" case —
        # the new interval reaches the end still in my hand
        res.append(newInterval)
        return res

Time: O(n) / Space: O(n) for the output (auxiliary O(1))

The final append trips people up: the elif only places the new interval when something comes after it. If it belongs at the end, absorbs everything, or the list is empty, the loop finishes with it unplaced. Same pattern as leftover openers in Valid Parentheses — the loop can end with unfinished business in your hand.

253. Meeting Rooms II — Three Ways

Minimum conference rooms needed. The key mental shift from Merge Intervals: overlapping meetings don't merge — they scatter into separate rooms and run simultaneously. So instead of tracking one end, I'm tracking many ends, one per occupied room.

Way 1 — Min-Heap

When a new meeting arrives, which room do I check? Common sense: the one that frees up earliest. If even that one isn't free, no room is — every other room ends later. One value decides everything, and "repeatedly give me the smallest of a changing set" is precisely a min-heap.

import heapq
 
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
 
        intervals.sort(key=lambda i: i[0])
 
        rooms = []   # min-heap of end times, one per occupied room
 
        for start, end in intervals:
            if rooms and rooms[0] <= start:
                # earliest-ending room is done — reuse it.
                # <= : ending at 13 frees the room for a
                # meeting starting at 13
                heapq.heappop(rooms)
 
            heapq.heappush(rooms, end)
 
        # reuse = pop+push (size unchanged), new room = push only —
        # so the final size is the peak room count
        return len(rooms)

Time: O(n log n) / Space: O(n)

Way 2 — Two Pointers (no heap)

The heap knows which meeting ends when — but look at the answer: it's just a number. I never need identities, only counts. So break every meeting into two events — "+1 running" at its start, "−1 running" at its end — sort starts and ends separately, and sweep both lists in time order:

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        starts = sorted(i[0] for i in intervals)
        ends = sorted(i[1] for i in intervals)
 
        res = count = 0
        s = e = 0
        while s < len(intervals):
            if starts[s] < ends[e]:
                count += 1      # next event in time: a start
                s += 1
            else:
                count -= 1      # next event: an end (ties end first)
                e += 1
            res = max(res, count)
        return res

Time: O(n log n) / Space: O(n)

The comparison starts[s] < ends[e] is just asking "which event happens next in time?" — the same merge step as merge sort. Losing the start-end pairing is fine because identities don't matter: it's counting people through a door, not tracking who's inside.

Way 3 — Bucket Array (when time is small and bounded)

If times are minutes in a day (0–1440), skip sorting entirely. Draw one slot per minute on a wall. Every meeting drops +1 in its start slot and −1 in its end slot — no sorting, just indexing. Then one left-to-right walk accumulates the count; the wall is already in time order.

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        diff = [0] * 1441
 
        for start, end in intervals:
            diff[start] += 1     # a meeting turns on here
            diff[end] -= 1       # a meeting turns off here
 
        res = count = 0
        for change in diff:
            count += change
            res = max(res, count)
        return res

Time: O(n + T) — effectively linear / Space: O(T)

This is the counting sort idea wearing an interval hat: use the value itself as the array index, and ordering comes for free. Same fine print too — the range must be small enough to allocate. Minutes in a day (1,440) or road stations (1,001 in Car Pooling) — easily. Unix timestamps — no; back to sorting or a tree.

Also notice: at a slot where one meeting ends and another starts, the −1 and +1 cancel before the count is read — back-to-back meetings share a room automatically. The heap's <= and the two-pointer's tie-branch encode the same rule by hand.

Follow-up: Room ID Assignment (which room does each meeting get?)

The two-pointer and bucket versions threw identity away — they can't answer this. The heap can, with one change: entries become (end, roomId) pairs. Tuples compare element by element, so the heap still ranks by end time — but now popping tells me who I'm reusing.

import heapq
 
class Solution:
    def assignRooms(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda i: i[0])
 
        busy = []          # (end_time, room_id)
        nextRoom = 0
        assignment = []
 
        for start, end in intervals:
            if busy and busy[0][0] <= start:
                _, roomId = heapq.heappop(busy)   # reuse — keep the id
            else:
                roomId = nextRoom                 # open a new room
                nextRoom += 1
 
            heapq.heappush(busy, (end, roomId))
            assignment.append([start, end, roomId])
 
        return assignment   # nextRoom == total rooms used

Time: O(n log n) / Space: O(n) — identity costs nothing asymptotically.

Bonus from tuple comparison: ties on end time break by room id automatically — which is exactly the "lowest numbered room" rule that Meeting Rooms III makes explicit. This variant is the on-ramp to that problem.

1094. Car Pooling — Meeting Rooms II with Weights

A car drives east only, picking up and dropping off passengers along a fixed route. Given trips[i] = [numPassengers, from, to] and a capacity, return whether the car can complete every trip without exceeding capacity.

Same shape as Meeting Rooms II — overlapping trips don't merge, they stack, and the only question is whether the peak ever crosses a limit. The one difference: instead of +1/-1 per meeting, each trip adds or removes numPassengers.

Way 1 — Bucket Array (bounded coordinates)

Stations are constrained to 0 <= from < to <= 1000. Small enough to skip sorting entirely — one slot per station, drop +p and -p stickers, walk the road left to right.

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        diff = [0] * 1001
 
        for p, start, end in trips:
            diff[start] += p     # passengers get in
            diff[end] -= p       # passengers get out
 
        count = 0
        for change in diff:
            count += change
            if count > capacity:
                return False
 
        return True

Time: O(n + 1001) — effectively O(n) / Space: O(1001) — effectively O(1)

Same trick as Meeting Rooms II's bucket array: the station number itself is the index, so ordering is free. One detail resolves itself for free too — at a station where one group gets off and another gets on, -p and +p land in the same slot and cancel before the running total is read. That's what enforces "drop off before picking up."

Way 2 — Sorted Events (unbounded coordinates)

If station numbers weren't small and bounded, fall back to sorting events directly — the general-purpose version of the same sweep.

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        events = []
        for p, start, end in trips:
            events.append((start, p))     # pickup
            events.append((end, -p))      # drop-off
 
        events.sort()
 
        count = 0
        for _, change in events:
            count += change
            if count > capacity:
                return False
        return True

Time: O(n log n) / Space: O(n)

Tuples sort by their first element, and on a tie by the second — so -p sorts before +p at the same coordinate. Storing drop-offs as negative numbers isn't just bookkeeping, it's what makes the sort itself enforce the ordering rule.

Way 3 — Min-Heap (which trip breaks capacity?)

Neither version above can answer "which trip caused the overflow" — a bucket array just accumulates numbers, and sorted events lose the connection back to a specific trip once split into two entries. To keep identity, process trips one at a time, in pickup order, with a min-heap tracking who's currently on board.

class Solution:
    def firstFailingTrip(self, trips: List[List[int]], capacity: int) -> int:
        sortedTrips = sorted(
            (start, end, p, i) for i, (p, start, end) in enumerate(trips)
        )
 
        onboard = []  # min-heap of (drop_off, passengers)
        count = 0
 
        for start, end, p, i in sortedTrips:
            # release everyone whose stop has already passed —
            # a while loop, not an if, because the gap between
            # two pickups can span more than one drop-off point
            while onboard and onboard[0][0] <= start:
                _, leaving = heapq.heappop(onboard)
                count -= leaving
 
            count += p
            if count > capacity:
                return i
 
            heapq.heappush(onboard, (end, p))
 
        return -1

Time: O(n log n) / Space: O(n)

The heap holds (drop_off, passengers) pairs — same "sort key plus payload" pattern as tagging Meeting Rooms' heap entries with a room id. The while instead of if matters in a way it didn't in Meeting Rooms II: there, the heap's size was the answer, so reusing exactly one room per meeting was the point. Here, count has to match the real number of passengers at every step, so every stop that's been passed gets settled — not just one.

2402. Meeting Rooms III — Two Heaps, Delayed Starts

n rooms, numbered 0 to n-1. Each meeting goes to the lowest-numbered empty room. If no room is free, the meeting waits for whichever room frees up first — and keeps its original duration, just starting later. Return the room that held the most meetings (ties → lowest room number).

Same family, one new twist: assignment now depends on both "is anything free" and "which specific room number." That needs two heaps instead of one:

• available — a min-heap of empty room ids, so "lowest free room" is a peek away
• busy — a min-heap of (end_time, room_id), same pairing trick as Room ID Assignment above

import heapq
 
class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort()
 
        available = list(range(n))
        heapq.heapify(available)
 
        busy = []          # (end_time, room_id)
        count = [0] * n
 
        for start, end in meetings:
            duration = end - start
 
            # free every room whose meeting already ended —
            # while, not if: more than one room can finish
            # in the gap since the last meeting's start
            while busy and busy[0][0] <= start:
                _, roomId = heapq.heappop(busy)
                heapq.heappush(available, roomId)
 
            if available:
                roomId = heapq.heappop(available)
                heapq.heappush(busy, (end, roomId))
            else:
                # no room free — reuse whichever frees up soonest,
                # keep the ORIGINAL duration, not the original end
                freeAt, roomId = heapq.heappop(busy)
                heapq.heappush(busy, (freeAt + duration, roomId))
 
            count[roomId] += 1
 
        best = 0
        for i in range(1, n):
            if count[i] > count[best]:
                best = i
        return best

Time: O(m log(m + n)) / Space: O(n)

The trap: freeAt + duration, not freeAt + end and not the original end. A delayed meeting keeps its length, not its original finish line. The while loop is the exact same reasoning as Car Pooling's release loop — the gap between two meetings' start times can span more than one room finishing.

count[roomId] += 1 runs once per meeting no matter which branch was taken, because both branches write the final room choice into the same variable name before the line executes — the assignment made there is never revisited, so counting it immediately is safe.

Verbal Follow-ups Worth Rehearsing

• Streaming bookings? Can't sort upfront — both sweep approaches break. Use a structure that keeps itself sorted: a balanced BST mapping time points to +1/−1, inserting in O(log n). Re-walking for the max is O(n) per booking; augmenting nodes with subtree sums (a segment tree) brings it to O(log n). This is LeetCode's My Calendar series.
• Can one person attend all meetings? That's Meeting Rooms I — sort, then check each neighbor pair. One pass.

Summary

The organizing question for the whole family: do you need WHO, or just HOW MANY? Counts → sweep or bucket. Identities → heap with ids. And the sweep itself is one logic with three ways to line events up in time order: sort them (two pointers), index them (bucket array), or maintain them in a self-sorting tree (streaming). Car Pooling is the same family with weighted events instead of unit events. Meeting Rooms III adds a second heap because now both "is a room free" and "which specific room" matter at once.