Problem
Given an array of meeting time intervals intervals, return the minimum number of conference rooms required.If one meeting ends exactly when another meeting begins, the same room can be reused.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
intervals = [[0,30],[5,10],[15,20]]Output
2Room 1: [0--------------------30]
Room 2: [5--10] [15--20]
Solution
This solution first sorts the meetings by their start time. A Min Heap is then used to track the end times of meetings currently occupying rooms.For each meeting, we compare its start time with the earliest ending meeting, which is always at the top of the heap. If that meeting has already ended, its room can be reused and its end time is removed from the heap.
The current meeting's end time is then added to the heap. The heap size represents the number of rooms currently required, and the maximum size needed during processing is the minimum number of meeting rooms required.
public int minMeetingRooms(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int[] meeting : intervals) {
// Reuse the room if the earliest meeting has ended.
if (!minHeap.isEmpty() && meeting[0] >= minHeap.peek()) {
minHeap.poll();
}
// Reserve a room until the current meeting ends.
minHeap.offer(meeting[1]);
}
return minHeap.size();
}
Complexity
Sorting the n meetings takesO(n log n) time. Each meeting is added to and removed from the Min Heap at most once, with each operation taking O(log n) time. Therefore, the overall time complexity is O(n log n).
In the worst case, all meetings overlap, so the heap stores
n end times and requires O(n) extra space.