Meetings Room 2

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.

Input:
Meetings: [[4,5], [2,3], [2,4], [3,5]]
Output:
2
Explanation:
We will need one room for [2,3] and [3,5], and another room for [2,4] and [4,5].

Let us visualize it.

Meetings Room thought Process

A person can not attend two or more meetings at one time in one room. It means if any meeting is going on in one room and another meeting starts before the end of the previous meeting, we need to allocate a different room to that meeting.
So, In this problem, we have to find out how many minimum rooms required to hold all meetings. This A simple way to solve this problem is to allocate a different room if the current meeting timings are clashing with the previous meeting timings. We have to Sort the meetings according to their starting time so that we can able to schedule the meetings and allocate the rooms according to it.

We will schedule the meeting M1 in one room R1. If the next meeting M2 is not clashing with the first meeting we can continue it in M1 room(no need to allocate the different room for it). If the next meeting M3 is clashing with M2, we can not allocate the same room R1 to that meeting, we have to allocate different room R2 to it. If meeting M4 is overlapping with the meeting M3, then we need to see if the room R1 has become free or not. For this, we need to keep track of the end time of the meeting happening in it. If the end time of M2 is before the start time of M4, we can use that room R1, otherwise, we need to schedule (M4 in another room R3.

The one way is to iterate through all the rooms and check if that room is empty or not. If any previous allocated room is empty, schedule that meeting in that room otherwise allocates a new room for it. Let’s think like that, most probably that meeting in the meeting room comes to an end whose ending time is less. Are you getting that point? It means we have to check among previous meetings which meeting has less ending time. We have one data structure that gives us the smallest element in constant time, its name is min-heap. We can keep all the rooms in a min-heap where the key for the min-heap would be the ending time of the meeting. Before allocating the new room to any meeting we will check the top element of the min-heap, if the top element(room containing the end time) is less than the start time of the meeting, go allocate that particular room to the meeting otherwise allocate the new room.

Algorithm

  1. Sort all the meetings on the basis of the start time.
  2. Create a min-heap add the first meeting’s ending timing to the heap.It will keep track when a meeting room will get free.
  3. For every meeting, check the top element of heap(smallest element).
    • If the top element of the heap is less than the current meeting start timing, then we extract the topmost element and push the ending timing of the current meeting.
    • else we will allocate a new room and push the ending time into the heap.
  4. Every time we allocate a new room, increement the counter which will let you know that how many rooms we needed.
class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        int i,j;
        
        if(intervals.size()==0)
        {
            return 0;
        }
        sort(intervals.begin(), intervals.end());
        priority_queue<int, vector<int>, greater<int>> pq;
        int count=0;
        
        for(i=0;i<intervals.size();i++)
        {
            if(pq.size()==0)
            {
                count=count+1;
                pq.push(intervals[i][1]);
            }
            else if(pq.size()!=0 && pq.top() <= intervals[i][0])
            {
                pq.pop();
                pq.push(intervals[i][1]);
            }
            else
            {
                count=count+1;
                pq.push(intervals[i][1]);
            }
        }
        return count;
        
    }
};

Time Complexity of the implementation is O(N*logN), where N is the total number of meetings. This is due to the sorting that we did in the beginning. Also, while iterating the meetings we might need to add meeting to the priority queue. It takes O(logN). Overall it takes O(NlogN). Space Complexity is O(N)