709989. Maximum Meetings in One Room
Maximum Meetings in One Room
Slug: maximum-meetings-in-one-room Difficulty: Medium Id: 709989 Topic Tags: Arrays, Greedy, Sorting, Data Structures, Algorithms Company Tags: None
Summary
The problem is to find the maximum number of meetings that can be held in a single room given a list of meeting start and end times. The goal is to schedule as many meetings as possible without any conflicts.
Detailed Explanation
To solve this problem, we will use a greedy approach with sorting. First, we sort all the meetings by their end times. Then, we iterate over the sorted meetings and select the ones that do not conflict with each other. A meeting does not conflict if its start time is greater than or equal to the end time of the previously selected meeting.
Here's a step-by-step breakdown:
- Sort the meetings by their end times.
- Initialize an empty list
scheduled_meetingsto store the scheduled meetings. - Iterate over the sorted meetings:
- For each meeting, check if it does not conflict with the previously scheduled meetings (i.e., its start time is greater than or equal to the end time of the last scheduled meeting).
- If the meeting does not conflict, add it to the
scheduled_meetingslist.
- Return the length of the
scheduled_meetingslist as the maximum number of meetings that can be held.
Time complexity: O(n log n) due to sorting Space complexity: O(n) for storing the scheduled meetings
Optimized Solutions
Java
import java.util.Arrays;
import java.util.List;
public class MaximumMeetings {
public static int maxMeetings(int[][] meetings) {
Arrays.sort(meetings, (a, b) -> a[1] - b[1]);
List<int[]> scheduledMeetings = new ArrayList<>();
int lastEndTime = 0;
for (int[] meeting : meetings) {
if (meeting[0] >= lastEndTime) {
scheduledMeetings.add(meeting);
lastEndTime = meeting[1];
}
}
return scheduledMeetings.size();
}
}