Coding Interview: Minimum Meeting Rooms

Prompt and use cases

You are given an unsorted array intervals. Each element is an integer time interval [start, end): start is included and end is excluded. A meeting that ends at time t therefore releases its room for another meeting starting at t. Assume 0 <= intervals.length <= 100000 and 0 <= start < end <= 1000000000. Return the minimum number of rooms required to schedule every meeting.

For example, [[0, 30], [5, 10], [15, 20]] returns 2; [[1, 5], [5, 8]] returns 1; an empty array returns 0. These are the interview constraints adopted by this article, not hidden limits attributed to any platform.

Public material provides several kinds of representative evidence. PracHub updated the same prompt in 2026. interviewing.io presents minimum meeting rooms as an interval problem solvable with a timeline or priority queue. One public interview account from February 2026 records follow-ups on two pointers, a priority queue, and an array for a bounded time domain. UMass algorithm notes provide the core interval-partitioning proof: when intervals are processed by start time, the number of rooms used by the greedy algorithm equals maximum overlap depth. A single account proves only that candidate's experience, so this article neither infers general interview frequency nor assigns the question to one company's fixed question bank.

Interviewer evaluation criteria

The first signal is modeling. This is a resource-counting problem, not interval merging and not selecting the largest compatible subset. The minimum room count equals the peak number of meetings in progress at any instant, often called the depth of the interval set.

The second signal is endpoint semantics. With half-open intervals, an end event must be processed before a start event at the same time. Treating start === end as an overlap incorrectly assigns two rooms to [1, 5) and [5, 8).

The third signal is invariants and proof. Once starts and ends are sorted separately, the pointers no longer preserve which end belongs to which meeting. A candidate should explain why identity is irrelevant when only concurrent occupancy matters: it is enough to know whether the next event is the earliest remaining start or end.

Finally, the interviewer can test data-structure choices under changing requirements. The two-array sweep returns the count directly. A request for concrete room assignments, the room used by each meeting, or a reuse history requires a min-heap that retains both end times and room identifiers.

Questions to clarify before answering

• Are intervals [start, end) or closed? This problem uses half-open intervals, so equal endpoints do not conflict.
• Are zero-length meetings valid? This contract requires start < end and rejects [t, t). If a business permits them, define whether they consume a resource.
• What should empty input return? Return 0, avoiding any first-meeting initialization error.
• Do we return only a count or also an assignment? Two arrays suffice for a count; assignment must retain meeting identity and reusable rooms.
• May the implementation mutate the input? The implementation below copies start and end values and leaves the caller's array untouched.
• Are times safe integers? The stated upper bound is within JavaScript's safe-integer range. Larger timestamps require a new representation contract.
• Can the input be invalid? Interview inputs usually satisfy the contract. Production validation belongs at the system boundary rather than inside the core algorithm.

30-second answer framework

“I would first confirm that the intervals are half-open, so a room released at a given time can be reused immediately. When only the minimum count is required, I sort starts and ends separately and scan them with two pointers. If the next start is strictly earlier than the earliest end, I increase occupancy; otherwise, I release a room first. I preserve the peak occupancy.

That peak is both a lower bound and achievable: simultaneous meetings require distinct rooms, and processing by start time opens a new room only when every existing room is still occupied. Sorting makes the total time O(n log n) with O(n) extra space. If the follow-up asks for a concrete assignment, I would use a min-heap containing end times and room identifiers.”

Step-by-step solution

Step 1: Compute peak occupancy from two sorted event streams

Put every start time into starts in ascending order and every end time into ends in ascending order. startIndex points to the next unprocessed start event, while endIndex points to the next unprocessed end event. roomsInUse is the number of rooms still occupied immediately after the current sweep position. Valid intervals satisfy start < end, so the sweep never processes an end while no meeting is active.

If starts[startIndex] < ends[endIndex], the next event is a start: increase occupancy and update the peak. Otherwise, process an end first and release one room. The strict less-than comparison is intentional. Equal endpoints take the release branch before the next start, exactly implementing [start, end).

export function minimumMeetingRooms(
  intervals: ReadonlyArray<readonly [number, number]>,
): number {
  if (intervals.length === 0) return 0

  const starts = intervals.map(([start]) => start).sort((a, b) => a - b)
  const ends = intervals.map(([, end]) => end).sort((a, b) => a - b)

  let startIndex = 0
  let endIndex = 0
  let roomsInUse = 0
  let maximumRooms = 0

  while (startIndex < intervals.length) {
    if (starts[startIndex] < ends[endIndex]) {
      roomsInUse += 1
      maximumRooms = Math.max(maximumRooms, roomsInUse)
      startIndex += 1
    } else {
      roomsInUse -= 1
      endIndex += 1
    }
  }

  return maximumRooms
}

Trace [[0, 30], [5, 10], [15, 20]]. The starts are 0, 5, 15; the ends are 10, 20, 30. Starts at 0 and 5 raise occupancy from 0 to 2. The end at 10 releases a room, reducing it to 1. The start at 15 raises it to 2 again. The peak is 2.

Step 2: Prove that the peak is the optimum

First, the sweep count is correct. Represent each [start, end) as a +1 start event and a -1 end event, sort by time, and process ends before starts on a tie. After any event, the running sum equals the number of intervals that still cover the timeline immediately afterward, which is precisely the number of occupied rooms. Merging two sorted arrays with pointers traverses all events in that order.

Next, prove that the peak is optimal. Let the maximum overlap depth be d. At some instant, d meetings run simultaneously, so every schedule needs at least d rooms; this is a lower bound. When meetings are processed by start time, the greedy assignment opens a new room only if all existing rooms are occupied by meetings that have not ended. If it opens room k, the new meeting and k - 1 others coexist at that instant, so k <= d. A schedule using only d rooms therefore exists. The feasible upper bound equals the lower bound, so the minimum is d, exactly the peak returned by the sweep.

Building the arrays costs O(n), the two sorts cost O(n log n), and the merge scan costs O(n). Total time is O(n log n) with O(n) extra space. If times come from a small, fixed discrete domain, a difference array can trade this for O(n + U) time and O(U) space. That optimization is unsuitable when the time bound is one billion.

Step 3: Choose a heap or difference array when requirements change

Another solution sorts meetings by start time and keeps the end time of every occupied room in a min-heap. Before processing a meeting, pop every entry with end <= start, then push the new end time. The peak heap size is the answer. This also takes O(n log n) time and O(n) worst-case space.

For a count alone, the sweep is shorter and exposes the rule that an end precedes a tied start. The heap is valuable for extensions: change each entry from end to { end, roomId }. Maintain a second min-heap of available room identifiers, reclaim identifiers after meetings end, and map each original meeting index to a concrete room. If the requirement says to choose the lowest-numbered available room, selecting only by earliest end is insufficient; occupied and available rooms must be managed separately.

Dynamic online booking is a different problem. When future meetings arrive individually and may be canceled, repeatedly sorting every interval may be too expensive. The query workload may require an ordered event store, interval tree, or calendar index. The O(n log n) offline-array answer should not be presented as a complete online system design.

High-quality sample answer

“I will solve this under [start, end), so a room can be reused when one end equals another start. Pairwise conflict checking is a valid baseline but costs O(n^2) in the worst case. With up to 100,000 meetings, I would sort events.

I create sorted start and end arrays. Two pointers determine the next event: an earlier start increments current occupancy and updates the maximum; an earlier or tied end decrements occupancy first. For [[0, 30], [5, 10], [15, 20]], occupancy changes through 1, 2, 1, and 2, so the answer is 2.

Correctness has two parts. The running sweep count equals the number of active intervals, so its maximum is overlap depth d. Every schedule needs at least d rooms when those meetings coexist. A start-time greedy assignment adds a room only while all existing rooms are occupied, so it never uses more than d. The algorithm is optimal. It takes O(n log n) time and O(n) space. If I need each meeting's room identifier, I will retain original indices and assign rooms with an end-time heap plus an available-identifier heap.”

Common mistakes

• Mistake: Solve interval merging. Why it fails: The number of merged intervals does not determine peak concurrent occupancy. Fix: Sweep start and end events and preserve the active-count peak.
• Mistake: Process a start before an end on equal endpoints. Why it fails: A room that can be reused immediately is counted twice. Fix: Give end events priority under the half-open contract.
• Mistake: Use JavaScript's default sort. Why it fails: Lexicographic order places 10 before 2. Fix: Pass (a, b) => a - b explicitly.
• Mistake: Return the final roomsInUse. Why it fails: Final occupancy can be lower than an earlier peak. Fix: Update maximumRooms on every start.
• Mistake: Compare every pair of meetings. Why it fails: Worst-case time becomes O(n^2). Fix: Sort and merge the two event streams linearly.
• Mistake: Pop only one finished meeting while producing assignments. Why it fails: The active and available sets become incomplete. Fix: Pop every room with end <= start and manage reusable identifiers separately.
• Mistake: Leave interval boundaries undefined. Why it fails: Tests will disagree on equal endpoints. Fix: Define half-open or closed intervals and tied-event priority before coding.
• Mistake: Add a company attribution from a public question-bank label. Why it fails: Third-party tags and one candidate account do not prove fixed ownership. Fix: Keep companyName as null when evidence is insufficient and state only what each source supports.

Follow-up questions and responses

Why may the two sorted arrays discard meeting correspondence?

The objective depends only on active-meeting count at each instant. The next count change is determined by the earliest unprocessed start and earliest unprocessed end, regardless of which meeting owns that end. Correspondence becomes necessary again for assignments or per-meeting traces, so use a heap containing meeting indices and room identifiers for those requirements.

What changes for closed intervals [start, end]?

An end and a start at the same time conflict. The comparison must process the start first, increasing occupancy when start <= end. The safer explanation is to define tie priority explicitly rather than mechanically changing an operator.

How would you return a room identifier for every meeting?

Retain original indices and sort by start time. Keep occupied rooms in a min-heap of { end, roomId }. Before each meeting, move every room with end <= start into a min-heap of available identifiers. Reuse the smallest available identifier or create a new one, then record assignment[originalIndex] = roomId.

Why does minimum room count equal maximum overlap?

Maximum overlap is an unavoidable lower bound because simultaneous meetings cannot share rooms. The start-time greedy algorithm opens a room only when every existing room is still occupied. Each room it opens therefore corresponds to the same number of meetings overlapping at that instant, so it never exceeds the lower bound. Equality proves optimality.

Which edge cases should be tested?

At minimum, test an empty array, one interval, no overlap, complete overlap, chains of equal endpoints, identical starts, identical ends, duplicate intervals, reverse-sorted input, and randomized data near the size limit. A small O(n^2) or discrete-event oracle can support randomized differential testing, but one-off verification code should not be mixed into the production implementation.

Can a small time domain produce a linear-time solution?

Yes. Use a difference array of size proportional to time domain U, add one at each start, subtract one at each end, and take the peak prefix sum. Its complexity is O(n + U) time and O(U) space. It is worthwhile only when U is small and memory is controlled; sorting is safer under the current one-billion bound.