Solution: Problem Challenge 1: Minimum Meeting Rooms

Problem Statement

Given a list of intervals representing the start and end time of ‘N’ meetings, find the minimum number of rooms required to hold all the meetings.

Example 1:

Meetings: [[1,4], [2,5], [7,9]]
Output: 2
Explanation: Since [1,4] and [2,5] overlap, we need two rooms to hold these two meetings. [7,9] can occur in any of the two rooms later.

Example 2:

Meetings: [[6,7], [2,4], [8,12]]
Output: 1
Explanation: None of the meetings overlap, therefore we only need one room to hold all meetings.

Example 3:

Meetings: [[1,4], [2,3], [3,6]]

.....

Like the course? Get enrolled and start learning!

Em Eff

· a year ago

With what looks like possible non-heap solutions posted, I'm not sure why the official solution uses one.

Here's a solution that leverages a Queue (or an array for simplicity's sake.) It basically just removes all meetings that start before the current then, after adding the current meeting to the queue, counts the max number rooms in use at any given time.

class Solution {
  findMinimumMeetingRooms(meetings) {
    let minRooms = 0

    meetings = meetings.sort((a, b) => a.start - b.start)

    const queue = []

    for(let meeting of meetings) {
      while(queue.length && queue[0].end <= meeting.start) {
        queue.shift()
      }

      queue.push(meeting)
      minRooms = Math.max(minRooms, queue.length)
    }

    return minRooms
  }
}