Meeting Rooms II

Medium

Problem

Given meeting time intervals, return the minimum number of conference rooms needed to hold them all. A meeting ending at t frees its room for one starting at t.

Example 1

Input:  [[0,30], [5,10], [15,20]]
Output: 2

Example 2

Input:  [[7,10], [2,4]]
Output: 1

Test cases

Case 1

Input:    [[0,30],[5,10],[15,20]]
Expected: 2

Case 2

Input:    [[7,10],[2,4]]
Expected: 1

Case 3

Input:    [[1,5],[5,10]]
Expected: 1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Sorted starts and ends (sweep)

Time O(n log n)Space O(n)

Walk starts in order. If a meeting has ended by this start, reuse its room (advance the end pointer); otherwise open a new room.

function minMeetingRooms(intervals) {
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, j = 0;
for (const s of starts) {
if (s < ends[j]) rooms++;
else j++;
}
return rooms;
}

Equivalent: sort by start and keep a min-heap of end times; the heap size is the answer.