Logic Explained: Meeting Scheduler - Leetcode [Java] using Priority Queue

Follow Me, Shout Out, or Give Thanks!

Please 💖 this article. a small thing to keep me motivated =)
Twitter: @djjasonclark
Linkedin: in/clarkngo

Description

Given an array of meeting time intervals where intervals[i] = [start_i, end_i], 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

Example 3:

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

Scenario

Today, your co-workers from different teams have given you a list of meeting start times and meeting end times. Setting up new rooms for a meeting is a pain so you'd want to reuse rooms that have been freed up by a previous meeting. You are tasked to find out how many rooms will be used.

Logic

1. Initially no rooms are occupied, so we insert the first earliest start time.

2. For subsequent meetings, check existing rooms are freed up, if yes, reuse the rooms. If not, then open up a new room.

Data Structure: Priority Queue

• The head of the priority queue is the least element based on the natural ordering or comparator based ordering. When we poll the queue, it returns the head object from the queue.

Pseudocode

1. Sort the intervals array in ascending order of the starting time. Use Arrays.sort() with Comparator in the 2nd parameter.

2. Create a Priority Queue. We will use this to store ending times of each interval. Use PriorityQueue data structure. Why Priority Queue? To make sure that when we check the head of the queue, we see the earliest end time at the head of the queue. This makes it efficient to check if we can reuse the room.

3. Add the end of time of the first sorted interval array.

4. Iterate over interval array starting at index 1.
   
   a. Check if starting time in i-th interval array is equal or greater than the end time at the head of the queue queue.peek(), then remove the end time the head of the queue queue.poll().
   
   b. Add the end of time of the i-th sorted interval array. queue.offer(). Note: in Priority Queue, we insert a new element at an index of the queue based on natural order.

5. Return the size of queue.

Scenarios

Scenario 1: the earliest end time in the queue is NOT greater than or equal to new meeting start time.

Scenario 2: the earliest end time in the queue is greater than or equal to new meeting start time.

Code

Solution from leetcode username: titasdatta93

Time Complexity: O(nlogn) Space Complexity: O(n)

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        //First sort the intervals in asc. order of starting time

        //TC: Of the below step : O(nlogn)
        Arrays.sort(
            intervals, 
            (Comparator<int[]>) (o1, o2) -> (o1[0] - o2[0])
        );

        //Create priority queue to store ending times of each interval
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        //Add the ending time of first sorted interval
        queue.offer(intervals[0][1]);

        for(int i=1; i<intervals.length; i++) {
            if(intervals[i][0] >= queue.peek()) {
                queue.poll(); //Poll from min heap happens in O(n) time
            }

            queue.offer(intervals[i][1]);
        }     //hence total time complexity here is O(logn) 

        return queue.size();
    }
}