876431. Meeting Rooms II
Meeting Rooms II
Slug: attend-all-meetings-ii
Difficulty: Medium
Id: 876431
Topic Tags: Heap, Greedy, Sorting, two-pointer-algorithm, Arrays
Company Tags: None
Summary
The Meeting Rooms II problem involves scheduling meetings in a set of rooms. You are given an array of meeting start and end times, and you need to find the minimum number of rooms required such that no two meetings overlap within the same room.
Detailed Explanation
To solve this problem, we can use a greedy algorithm with a priority queue (heap). We first sort the meeting intervals by their start time. Then, we iterate over the sorted array and for each interval, we check if it overlaps with any of the previous intervals assigned to the same room. If it does not overlap, we assign it to an available room. If it does overlap, we need a new room.
Here is a step-by-step breakdown:
- Initialize a heap (priority queue) to store the end times of the meetings.
- Sort the meeting intervals by their start time.
- Iterate over the sorted array and for each interval:
- If the heap is empty or the current meeting starts after the earliest meeting in the heap, assign it to an available room (add its end time to the heap).
- Otherwise, check if the current meeting overlaps with any of the previous meetings in the same room. If it does not overlap, assign it to the same room.
- The size of the heap at the end represents the minimum number of rooms required.
Time complexity: O(n log n) due to sorting and priority queue operations. Space complexity: O(n) for storing the meeting intervals and priority queue elements.
Optimized Solutions
Java
import java.util.*;
public class Solution {
public int minMeetingRooms(int[][] intervals) {
if (intervals.length == 0) return 0;
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> queue = new PriorityQueue<>();
int roomsUsed = 0;
for (int[] interval : intervals) {
if (!queue.isEmpty() && queue.peek() <= interval[0]) {
queue.poll();
}
queue.add(interval[1]);
roomsUsed = Math.max(roomsUsed, queue.size());
}
return roomsUsed;
}
}