HARD Lab · Intervals · 52

253. Meeting Rooms II

Find the minimum number of conference rooms needed to schedule all meetings without conflict by sweeping independently-sorted start times and end times with two pointers — whenever a new meeting begins before the earliest one ends, you need an extra room; otherwise, recycle.

● MediumSweep LineTwo PointersTypeScript

PROBLEM What we're solving

Given a list of meeting intervals [[start, end], …], return the minimum number of conference rooms required so every meeting can run simultaneously with no overlap. For [[0,30],[5,10],[15,20]] the answer is 2: meetings 5–10 and 15–20 can share room B, but 0–30 must hold room A throughout.

KEY IDEA Sort starts and ends independently, then sweep

Insight → We do not need to know which meeting ends; we only need to know whether any meeting has ended. Sort starts and ends into two separate arrays. At each start event, compare it against the smallest active end time. If the new meeting starts before that end, you need one more room. Otherwise, the earliest-ending meeting is done — recycle its room. Track the running maximum of rooms in use; that is the answer.

RECIPE Two-pointer sweep over sorted starts & ends

  • 0 · Sort separately. starts[] and ends[] — because we care only about event counts, not pairing.
  • 1 · Two pointers si, ei. Advance si through every start event (we must process each meeting). ei only advances when we free a room.
  • 2 · starts[si] < ends[ei]? No meeting has ended yet — allocate a new room. rooms++; update maxRooms.
  • 3 · Otherwise. The earliest-ending meeting finished before or exactly when this one starts — recycle it. rooms--; ei++.
  • 4 · Answer is maxRooms. The peak concurrent rooms is the minimum number of rooms needed.
Classic confusion → why sort independently? If you sort by start and try to track which end goes with which meeting, you end up simulating a min-heap. The two-pointer trick works because we only need to know "has any meeting ended?" — not which one. The independently-sorted ends[] always exposes the smallest active end, which is the only comparison we need.

COST Complexity & alternatives

Min-heap on end times
O(n log n)
Sort once; push/pop per event. Same asymptotic, bigger constant.
Two-pointer sweep
O(n log n)
Sort twice; O(1) per event. No heap overhead.

Both approaches are O(n log n) time (dominated by sorting) and O(n) space. The two-pointer solution is typically faster in practice because array traversal beats heap operations by a constant factor.

Pattern transfer →the same "sort starts and ends independently and count the overlap peak" idea solves Maximum CPU Load, Employee Free Time, and Number of Flowers in Full Bloom. Any time you need the maximum number of simultaneously-active intervals, this sweep applies directly.

RUN IT Sweep sorted starts & ends with two pointers

step 0 / 5
STARTSort starts and ends independently. starts = [0, 5, 15], ends = [10, 20, 30]. Walk both with two pointers: a start event needs a room; an end event frees one.
starts →0s05s115s2
State
0
rooms
0
max
0
si
0
ei
start event (need room)end event (free room)running max rooms
slowfast

TYPESCRIPT The solution, annotated

minMeetingRooms.ts
function minMeetingRooms(intervals: number[][]): number {
  const n = intervals.length;
  if (n === 0) return 0;

  const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
  const ends   = intervals.map(i => i[1]).sort((a, b) => a - b);

  let rooms = 0;
  let maxRooms = 0;
  let ei = 0;

  for (let si = 0; si < n; si++) {
    if (starts[si] < ends[ei]) {
      // A new meeting starts before the earliest-ending meeting ends:
      // we cannot reuse any room, so we need a new one.
      rooms++;
      maxRooms = Math.max(maxRooms, rooms);
    } else {
      // The earliest-ending meeting has already finished by the time
      // this one starts, so we recycle that room.
      rooms--;
      ei++;
    }
  }

  return maxRooms;
}

Reading it block by block

Lines 4–5 — sort independently. Extract all start times into starts and all end times into ends, each sorted ascending. Sorting decouples the problem: we no longer need to track which meeting ends when.
Lines 7–9 — initialize state. rooms is the current number of rooms in use, maxRooms tracks the peak, and ei is the end-pointer (always points to the smallest active end time).
Lines 11–15 — start < earliest end. A meeting starts before any existing meeting ends, so we cannot reuse a room. Increment rooms and update maxRooms. Note we do not advance ei.
Lines 16–19 — start ≥ earliest end. At least one meeting has finished by the time this one starts. Recycle that room: decrement rooms and advance ei to the next end event.
Line 23 — return maxRooms. The maximum concurrent rooms at any moment equals the minimum number of rooms needed to hold all meetings without conflict.
Complexity → O(n log n) time (two sorts dominate); O(n) space for the two auxiliary arrays. The loop itself is O(n).

INTERVIEWFollow-ups they'll ask

  • "Min-heap alternative?" Sort by start; maintain a min-heap of end times. If heap.peek() ≤ start, pop and reuse the room; otherwise push the new end. The heap always holds O(rooms) entries. Same complexity but clearer pairing.
  • "Why does sorting ends independently work?" We never need to know which meeting ended — only whether any meeting with an end time before the current start exists. The smallest end time answers that question, regardless of which interval it came from.
  • "What if meetings have the same start and end?" The starts[si] < ends[ei] condition uses strict less-than, so a meeting ending exactly when another starts does not require an extra room — that room is recycled first.
  • "How would you extend to return which meetings share a room?" You'd need the min-heap approach, pairing each meeting with the room whose end time it recycles; the two-pointer trick loses interval identity.
  • "Related problems?" Car Fleet (count simultaneous queues), Number of Flowers in Full Bloom (same sweep), and Merge Intervals (find the overlapping groups).

MNEMONIC The one-liner

"Sort starts and ends separately; at every start, if it arrives before the earliest end, add a room — otherwise recycle."

TRIGGERS When you see ___ → reach for ___

"minimum rooms / resources for intervals"two-pointer sweep on sorted starts & ends
"peak concurrent intervals"count net +1/-1 events, track max
"any meeting ended before this one starts?"compare starts[si] < ends[ei]
"group overlapping intervals"sort by start; sweep line on ends

SKELETON The reusable shape

skeleton.ts
function minMeetingRooms(intervals: number[][]): number {
  const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
  const ends   = intervals.map(i => i[1]).sort((a, b) => a - b);

  let rooms = 0, maxRooms = 0, ei = 0;

  for (let si = 0; si < intervals.length; si++) {
    if (starts[si] < ends[ei]) {
      rooms++;
      maxRooms = Math.max(maxRooms, rooms);
    } else {
      rooms--;
      ei++;
    }
  }

  return maxRooms;
}

FLASHCARDS Tap to flip

Why sort starts and ends into two separate arrays?
We only need to know if any meeting has ended — not which one. Separate sorting exposes the smallest active end time at ends[ei].
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 7
QUESTION 01
For [[0,30],[5,10],[15,20]], what is the answer?
QUESTION 02
Why are starts and ends sorted independently rather than together?
QUESTION 03
What happens when starts[si] ≥ ends[ei]?
QUESTION 04
What is the time complexity of the two-pointer solution?
QUESTION 05
Meeting A ends at time 10 and meeting B starts at time 10. Do they need separate rooms?
QUESTION 06
What does maxRooms represent after the loop?
QUESTION 07
The min-heap alternative for this problem sorts intervals by: