Meeting Rooms II

Medium

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

Example 1:

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

Example 2:

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

This problem is very similar to something that employees of a company can face potentially on a daily basis. Suppose you work at a company and you belong to the IT department and one of your job responsibilities is securing rooms for meetings that are to happen throughout the day in the office. You have multiple meeting rooms in the office and you want to make judicious use of them. You don’t really want to keep people waiting and want to give a group of employees a room to hold the meeting right on time. At the same time, you don’t really want to use too many rooms unless absolutely necessary. It would make sense to hold meetings in different rooms provided that the meetings are colliding with each other, otherwise you want to make use of a few rooms as possible to hold all of the meetings. How do you go about it? The problem can be described as following.

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required. Lets revisit the first example given in the problem statement.

Example 1:

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

Consider the below figure to have a better understanding of the problem.

Schedule Meetings

So we need 2 Meeting Rooms to accommodate all 4 meetings

The most basic way of processing the meetings is in increasing order of their start times .We sort the meetings by their start and end value. Sorting part is easy, but for every meeting how do we find out efficiently if a room is available or not? When a room is taken, the room can not be used for another meeting until the current meeting is over. As soon as the current meeting is finished, the room can be used for another meeting. A naive way to check if a room is available or not is to iterate on all the rooms and see if one is available when we have a new meeting at hand.

We can use a Priority Queue or the Min-Heap data structure to find rooms where the ongoing meeting is finished.

Instead of manually iterating on every room that’s been allocated and checking if the room is available or not, 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. So, every time we want to check if any room is free or not, simply check the topmost element of the min-heap as that would be the room that would get free the earliest out of all the other rooms currently occupied. If the room we extracted from the top of the min-heap isn’t free, then no other room is. So, we can save time here and simply allocate a new room.

Let us look at the algorithm before moving onto the implementation.

Algorithm

  1. Sort the given meetings by their start time. If the start times are the same for two meetings then sort based on the end times.
  2. Initialize a new min-heap and add the first meeting’s ending time to the heap. We simply need to keep track of the ending times as that tells us when a meeting room will get free.
  3. For every meeting room check if the minimum element of the heap i.e. the room at the top of the heap is free or not.
  4. If the room is free, then we extract the topmost element and add it back with the ending time of the current meeting we are processing.
  5. If not, then we allocate a new room and add it to the heap.
  6. After processing all the meetings, the size of the heap will tell us the number of rooms allocated. This will be the minimum number of rooms needed to accommodate all the meetings.

Let us not look at the implementation of this algorithm.

class Meeting implements Comparable<Meeting>{
    
    int start;
    int end;
    
    public Meeting(int s, int e){
        start = s;
        end = e;
    }
    
    public int compareTo(Meeting m){
        if(this.start == m.start){
            return (this.end - m.end);
        }
        return (this.start - m.start);
    }
}

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if(intervals == null || intervals.length == 0 || intervals[0].length == 0){
            return 0;
        }
        List<Meeting> meetingList = new ArrayList<>();
        for(int[] interval : intervals){
            Meeting meeting = new Meeting(interval[0],interval[1]);
            meetingList.add(meeting);
        }
        Collections.sort(meetingList);
        Queue<Integer> minHeap = new PriorityQueue<>();
        for(Meeting meeting : meetingList){
            if(minHeap.isEmpty()){
                minHeap.offer(meeting.end);
            }else{
                int prevEnd = minHeap.peek();
                int curentStart = meeting.start;
                if(prevEnd <= curentStart){
                   minHeap.poll(); 
                }
                minHeap.offer(meeting.end);
            }
        }
        return minHeap.size();
    }
}

Complexity Analysis

  • Time Complexity: O(NlogN).
    • There are two major portions that take up time here. One is sorting of the array that takes O(NlogN) considering that the array consists of N elements.
    • Then we have the min-heap. In the worst case, all N meetings will collide with each other. In any case we have N add operations on the heap. In the worst case we will have N extract-min operations as well. Overall complexity being (NlogN) since extract-min operation on a heap takes O(logN).
  • Space Complexity: O(N) because we construct the min-heap and that can contain N elements in the worst case as described above in the time complexity section. Hence, the space complexity is O(N).

Categories: Heap

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s