876297. Meeting Rooms
Easy
Meeting Rooms
Slug: attend-all-meetings Difficulty: Easy Id: 876297 Topic Tags: Sorting, Greedy, Arrays Company Tags: None
Summary
We are given a list of meetings scheduled in ascending order based on the meeting start time. Each meeting has two participants and we need to determine the minimum number of rooms required such that all the meetings can be attended without any conflicts.
Detailed Explanation
To solve this problem, we will use a greedy algorithm approach. The idea is to always choose the next available meeting room for each new meeting.
Here are the steps:
- Create an empty list
roomsto store the end time of each meeting in a meeting room. - Iterate over the meetings and for each meeting:
- Find the earliest available meeting room by finding the smallest end time in the
roomslist. - If no rooms are available, add a new room with the current meeting start time as its end time.
- Update the end time of the chosen room to be the maximum of its current end time and the current meeting end time.
- Find the earliest available meeting room by finding the smallest end time in the
Time complexity: O(n log n) due to sorting
Space complexity: O(n) for storing the rooms list
Optimized Solutions
Java
import java.util.Arrays;
import java.util.Comparator;
public class MeetingRooms {
public int minMeetingRooms(int[][] intervals) {
if (intervals.length == 0) return 0;
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
int rooms = 1;
int end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= end) {
rooms++;
end = intervals[i][1];
} else {
end = Math.max(end, intervals[i][1]);
}
}
return rooms;
}