Coding

Meeting Rooms II

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

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

At time 0, the first meeting starts, so 1 room is required.
At time 5, the second meeting starts while the first one is still ongoing, so 2 rooms are required.
At time 10, the second meeting ends, freeing up one room, so 1 room is used.
At time 15, the third meeting starts, and the room count increases back to 2. Output: 2 (At the peak, two rooms are required.)

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

The first meeting starts at 2 and ends at 4, using 1 room.
The second meeting starts at 7 and ends at 10, and it doesn't overlap with the first one, so only 1 room is required. Output: 1 (Only 1 room is needed since there's no overlap between the meetings.)

Input : [[1,2],[11,20],[13,21],[7,21]]

1 <= intervals.length <= 104
0 <= starti < endi <= 106

cpp

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        // Your code goes here
    }
};

java

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        // Your code goes here
    }
}

python

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        # Your code goes here

javascript

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var minMeetingRooms = function(intervals) {
    // Your code goes here
};

csharp

public class Solution
{
    public int MinMeetingRooms(int[][] intervals)
    {
        // Your code goes here
    }
}

func minMeetingRooms(intervals [][]int) int {
	// Your code goes here
}

Stuck? Show a way to structure it+

01Sort meetings by start time.
02Keep a min-heap of active end times.
03Release rooms whose end is at or before the next start.
04Add the next end time.
05Track the largest heap size.

Reference answer

Sort meetings by start time and keep a min-heap containing end times of rooms currently occupied. Before placing a meeting, pop every end time <= meeting.start, since those rooms are reusable under the usual half-open convention. Push the current end; the heap size is the number of simultaneous meetings after that placement, so the maximum observed size is the minimum room count. Popping all available rooms makes the approach correct even when several meetings end before the next starts. Sorting and heap operations give O(N log N) time and O(N) space. An equally valid sweep-line solution sorts starts and ends separately, but the heap is easier to extend when room assignments are needed.

Then expect these follow-ups

How would you assign an actual room number?
Tests: heap bookkeeping
How does a two-array sweep compare?
Tests: tradeoffs

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question