### 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

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

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

Sort the

`intervals`

array in ascending order of the starting time.*Use Arrays.sort() with*.`Comparator`

in the 2nd parameterCreate 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.Add the end of time of the first sorted interval array.

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**, then remove the end time the head of the queue`queue.peek()`

.`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 orderReturn 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();
}
}
```

## Top comments (0)