Problem:
Given an array of meeting intervals , find the minimum number of conference rooms required .
For example,
If the meeting intervals are :
[[1,10],[2,15],[15,20]]
Then the number of rooms required are 2.
How?
First we allocate a meeting room for the first meeting [1,10].
It ends at 10.
The next meeting starts at 2.
But a meeting is already going on room 1.
So we allocate another room for the meeting [2,15]
The third meeting starts at 15.
By the time it starts , first meeting in the first room would have ended ([1,10])
So allocate the third meeting to the first room.
The total rooms required is thus 2.
Try out the solution here:
https://leetcode.com/problems/meeting-rooms-ii/
Solution:
Hint:
- Use a priority queue to store meeting endings in ascending order so that you know which room gets freed up first
Let’s look at two solutions to this problem:
Approach 1 : Using Priority Queues
We need to add a new meeting room if no other meetings which started before the current meeting has ended.
We need to use an existing meeting room if any other meeting has ended when the current meeting starts.
As mentioned we need to check if no other meetings which started before the current meeting has ended . To do this we need to first sort the meetings in ascending order according to the start times.
Let’s use a priority queue to store the end times of the meetings.
Whenever you find a new meeting if the queue is empty you add the end time to it.
Else you check if the earliest ending (which will be on top of the priority queue) is before the start of the current meeting.
If so you can use that meeting room instead of adding new one.
So you will pop the meeting end from the queue and add the current end to it.
Internally the priority queue will shuffle and maintain the earliest ending at the top.
If the earliest ending is greater than the current start time then it means no meeting rooms are available , so you add the current ending to the priority queue.
Finally the queue size will give the number of rooms required because you add to it only when you need a new room.
Let’s take the below input and test this:
(1,10) , (2,7) , (3,19) , (8,12) , (10,20) ,(11,30)
First you add the first interval end to the priority queue (min heap)
[10]
Next we take the next interval (2,7)
The start time 2 is less than the end time in the min heap (10) . So there is a meeting going on and you cannot use the existing room.
So you add a new room and add the new ending to the heap.
[7]
[10]
The priority queue will maintain the smallest number (earliest meeting end) at the top which is 7 now.
You then take the next meeting interval (3,19).
The start time 3 is less than the earliest end in the heap (7).
So you add a new meeting room (third) and add the end time to the heap.
The heap now becomes:
[7]
[10]
[19]
Now take the next meeting interval (8,12)
The start time 8 is greater than the earliest end in the heap (7)
So it means a meeting has ended and a room is free.
So use that room (pop the topmost value from heap and add the new end to it).
The meeting end 7 is popped out. And the new meeting end 12 is added.
[10]
[12]
[19]
The next meeting interval (10,20) has a start 10 which is equal to the earliest end on the heap.
If start and end coincide we consider that as non overlapping.
So use an existing room .
Pop out the ending from the heap and insert the new ending:
[12]
[19]
[20]
The last meeting interval has a start time 11.
This is less than the earliest ending on the heap.
So no rooms are available.
Hence add the new end to the heap:
[12]
[19]
[20]
[30]
The intervals are over now .
The queue size is 4 which gives the minimum number of meeting rooms required.
ALGORITHM:
STEP 1: If interval length is empty return zero
STEP 2: Sort the array based on start time
STEP 3: Create a priority queue to store end times
STEP 4: Add the first end to the priority queue
STEP 5: For each interval starting from the second interval , check if the start time is greater than or equal to the end time on the top of the priority queue.
STEP 5a: If so , pop it out and add the new end to it
STEP 5b: If start time is less than the earliest ending then new room is required so add the new ending to the priority queue.
Code:
class Solution {
public int minMeetingRooms(int[][] intervals) {
if(intervals.length == 0) return 0;
Arrays.sort(intervals, (a,b) -> Integer.compare(a[0],b[0]) );
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(intervals.length, (a,b) -> Integer.compare(a,b));
queue.add(intervals[0][1]);
for(int i=1;i<intervals.length;i++){
if(intervals[i][0] >= queue.peek()){
queue.poll();
}
queue.add(intervals[i][1]);
}
return queue.size();
}
}
Time complexity:
The initial sorting takes O(nlogn) where n is the number of intervals
At the worst case we may add all elements to the queue which takes O(n) time.
Finding the minimum element in the priority queue takes O(logn) time.
Total time complexity is O(nlogn)
Space complexity:
At the worst case all intervals could be added to the priority queue so space required is O(n)
Approach 2: Using sorted start times and end times
In the second approach , you sort the start times and end times separately.
You check each end time maintaining a pointer to the start times and end times.
If the end time is greater than current meeting start time then it means that the meeting has not ended and so the meeting room corresponding to that end time is not free . So you increase the count of rooms required for the current meeting and move to the next meeting start time.
If the end time is smaller than or equal to the current meeting start time then the meeting room has freed and you can use it for the current meeting. You do that , move to the next start time and also to the next end time (as the current meeting is going to use the corresponding room)
ALGORITHM:
STEP 1: If intervals is empty , return 0
STEP 2: Collect all start times and sort them in ascending order
STEP 3: Collect all end times and sort them in ascending order
STEP 4: Create two pointers to point to starting and ending times respectively from the beginning.
STEP 5: If start time is greater than or equal to the end time , then it means a room has freed and it can be used for current meeting , so increment start pointer and end pointer.
STEP 6: if start time is less than end time , then no room is available , so increment a room counter and move to next meeting by incrementing the start pointer.
STEP 7: Return the counter value.
Code:
class Solution {
public int minMeetingRooms(int[][] intervals) {
if(intervals.length == 0) return 0;
Integer[] startTimes = new Integer[intervals.length];
Integer[] endTimes = new Integer[intervals.length];
for(int i=0;i<intervals.length;i++){
startTimes[i] = intervals[i][0];
endTimes[i] = intervals[i][1];
}
Arrays.sort(startTimes,(a,b) -> Integer.compare(a,b));
Arrays.sort(endTimes, (a,b) -> Integer.compare(a,b));
int start = 0;
int end = 0;
int rooms = 0;
while(start < intervals.length){
if(startTimes[start] >= endTimes[end]){
end++;
}else{
rooms++;
}
start++;
}
return rooms;
}
}
Time complexity:
Time required for the two sorting is O(nlogn) + O(nlogn)
and then we make a pass through the array which takes O(n)
So total time complexity is O(nlogn)
Space complexity:
We use two arrays in proportion to the size of the array to store starting and ending times.
So space complexity is O(n) + O(n) which can be considered as O(n).
That’s it!
Leave a Reply