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() withComparator
in the 2nd parameter.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.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 queuequeue.peek()
, then remove the end time the head of the queuequeue.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.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();
}
}
Top comments (0)