## DEV Community is a community of 701,921 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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

Clark Ngo
Software Engineer | Teacher

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

#### Code

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