You are given an integer N which represents the total number of meetings. You are also given two integer arrays named start and end. The start array contains the scheduled beginning time for each meeting and the end array contains the exact time each meeting concludes. Your objective is to find the maximum number of meetings that can be accommodated in a single meeting room. A meeting room can only host one meeting at a time and a new meeting can strictly only begin after the previous one has completely finished.
Example 1
Input: start[] = [1, 3, 0, 5, 8, 5]end[] = [2, 4, 6, 7, 9, 9]
Output:4
Explanation: The meetings (1, 2), (3, 4), (5, 7), and (8, 9) can be selected.
So, the maximum number of meetings is 4.
Example 2
Input: start[] = [10, 12, 20]end[] = [20, 25, 30]
Output:1
Explanation: Every meeting overlaps with another in a way that allows only one meeting to be selected.
So, the answer is 1.
Brute Force Approach
For every meeting, there are only two choices:
Take this meeting.
Skip this meeting.
So, a simple brute force idea is to try all possible subsets of meetings using recursion.
But while taking a meeting, it must not overlap with any meeting already selected. If it overlaps, that meeting cannot be added to the current subset.
This approach is easy to understand because it directly checks all possibilities. The problem is that the number of subsets grows very fast. For n meetings, there can be 2^n possible subsets, so this method is useful for learning but not practical for large input.
Algorithm
Start from the first meeting and keep a list of meetings selected so far. This list helps check whether a new meeting can fit with the already chosen meetings.
At every index, first try the choice of skipping the current meeting. This is needed because the best answer may not include the current meeting.
Then check whether the current meeting can be added without overlapping with any selected meeting. This check is important because the room can hold only one meeting at a time.
If the meeting is valid, add it to the selected list and solve for the remaining meetings. After recursion returns, remove it so other possibilities can be tested cleanly.
Return the maximum count from both choices: taking the current meeting and skipping it.
Dry Run
N meetings in 1 Room Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: /* Checks whether the current meeting can be added without overlapping with already selected meetings. */ bool canTake(pair<int, int> current, vector<pair<int, int>>& selected) { for (auto meeting : selected) { /* If neither meeting ends strictly before the other starts, both meetings overlap and cannot use the same room. */ if (!(current.second < meeting.first || meeting.second < current.first)) { return false; } } return true; } /* Recursively tries all subsets and returns the maximum number of non-overlapping meetings. */ int solve(int index, vector<pair<int, int>>& meetings, vector<pair<int, int>>& selected) { /* When all meetings are processed, the current subset is complete and no more meetings can be added. */ if (index == meetings.size()) { return 0; } /* This choice skips the current meeting because the best answer may come from meetings after it. */ int skip = solve(index + 1, meetings, selected); int take = 0; /* The current meeting is taken only if it does not overlap with any meeting already selected. */ if (canTake(meetings[index], selected)) { selected.push_back(meetings[index]); take = 1 + solve(index + 1, meetings, selected); selected.pop_back(); } return max(take, skip); }public: /* Finds the maximum number of meetings by trying every possible subset recursively. */ int maxMeetings(vector<int>& start, vector<int>& end) { vector<pair<int, int>> meetings; for (int i = 0; i < start.size(); i++) { meetings.push_back({start[i], end[i]}); } vector<pair<int, int>> selected; return solve(0, meetings, selected); }};int main() { // Driver code starts vector<int> start = {1, 3, 0, 5, 8, 5}; vector<int> end = {2, 4, 6, 7, 9, 9}; Solution sol; cout << sol.maxMeetings(start, end); return 0;}Complexity Analysis
Time Complexity: O(n * 2n) because all subsets may be explored, and checking whether a meeting is compatible can take O(n) time.
Space Complexity: O(n) because the recursion stack and selected meetings list can store at most n meetings.
Optimal Approach
The important observation is this: A meeting that ends earlier leaves the room free earlier.
Suppose two meetings are available. If one meeting ends at time 4 and another ends at time 10, choosing the meeting that ends at 4 is usually better because it leaves more space for future meetings.
The start time alone is not enough. A meeting may start early but run for a very long time, blocking the room for many other smaller meetings.
So instead of choosing the meeting that starts earliest, the greedy idea is to choose the meeting that finishes earliest.
Once meetings are sorted by their ending time, each selected meeting gives the best possible chance to fit more meetings after it.
Algorithm
Store every meeting as a pair of start time and end time. This is done so that each meeting can be sorted and processed as one unit.
Sort all meetings by their end time. This is the main greedy step because the meeting that ends earlier keeps the room available for more future meetings.
Keep a variable
lastEndTimeto remember when the last selected meeting ended. This helps check whether the next meeting can fit after it.Go through the sorted meetings one by one. If the current meeting starts strictly after
lastEndTime, select it because it does not overlap with the previous selected meeting.Every time a meeting is selected, increase the answer and update
lastEndTimeto the current meeting’s end time. This prepares the room availability check for the next meetings.
Dry Run
NIMOR
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Finds the maximum number of meetings that can be scheduled in one room without overlapping. */ int maxMeetings(vector<int>& start, vector<int>& end) { int n = start.size(); /* Each meeting is stored with its end time first so sorting naturally arranges meetings by finish time. */ vector<pair<int, int>> meetings; for (int i = 0; i < n; i++) { meetings.push_back({end[i], start[i]}); } sort(meetings.begin(), meetings.end()); /* This stores the ending time of the last selected meeting. -1 allows the first valid meeting to fit. */ int lastEndTime = -1; /* This stores how many meetings have been selected so far. */ int count = 0; for (auto meeting : meetings) { int currentEnd = meeting.first; int currentStart = meeting.second; /* A meeting can be selected only when it starts strictly after the previously selected meeting ends. */ if (currentStart > lastEndTime) { count++; lastEndTime = currentEnd; } } return count; }};int main() { // Driver code starts vector<int> start = {1, 3, 0, 5, 8, 5}; vector<int> end = {2, 4, 6, 7, 9, 9}; Solution sol; cout << sol.maxMeetings(start, end); return 0;}Complexity Analysis
Time Complexity: O(n log n) because the meetings are sorted by their ending time.
Space Complexity: O(n) because an extra list of meetings is used for sorting.
Interview follow-up Questions
Sorting by start time can be a deadly trap. Imagine a meeting that starts at 8:00 AM and ends at 8:00 PM. If you sort by start time, you might pick this massive 12-hour meeting first, occupying the room for the entire day. Meanwhile, you could have fit ten separate 1-hour meetings into that exact same time frame. Sorting strictly by end time mathematically forces the algorithm to pick the meetings that free up the room as fast as physically possible.
Be the first to add a comment.