Logic Explained: Meeting Scheduler - Leetcode [Java] using Priority Queue
Tags: java, coding, leetcode, datastructure
Published: 2021-04-13 11:34:43

---
title: Logic Explained: Meeting Scheduler - Leetcode [Java] using Priority Queue
published: true
description: coding challenge - priority queue
tags: java, coding, leetcode, datastructure
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/it30emvb5ix8pcqngr7p.png
---

### Follow Me, Shout Out, or Give Thanks! 
Please :sparkling_heart: this article. a small thing to keep me motivated =)
Twitter: [@djjasonclark](https://twitter.com/djjasonclark)
Linkedin: [in/clarkngo](https://www.linkedin.com/in/clarkngo/)

#### Description

Given an array of meeting time `intervals` where `intervals[i] = [start`<sub>i</sub>`, end`<sub>i</sub>`]`, 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.<br/>
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()`_.<br/>
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.
![image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/urilyvu02jpjzp5wo2eu.png)
 
##### Scenario 2: the earliest end time in the queue is greater than or equal to new meeting start time.
![image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qcxrqrioick8wauwq1hc.png)

#### Code
[Solution](https://leetcode.com/problems/meeting-rooms-ii/discuss/1151560/Simple-Java-NlogN-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();
    }
}
```