Max Meetings in a Room Editorial

Practice Problem Link: Max Meetings in a Room | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given the start and finish time of n meetings and just one room to conduct them, find the maximum number of meetings that can be accommodated in that room.

Naive Approach

A simple solution is to check all combinations, and find a valid combination that gives the maximum answer. The time complexity for this approach will be exponential.

Analysis

• Time Complexity: O(n * 2ⁿ)
• Auxiliary Space Complexity: O(n)

Optimal Approach

A greedy approach can be used to solve this problem efficiently. The basic idea is to sort the meeting timings in increasing order according to the finish time of each meeting and pick a meeting whose start time is just greater than or equal to the finish time of one of the previous meetings.

• After sorting the timings as mentioned above, note the finish time of the first meeting and increment the answer by one.
• Traverse the array and as soon as a meeting is encountered whose start time is greater than or equal to the finish time of the first meeting. Increment the answer by one and note the finish time of the current meeting.
• Repeat the previous step while traversing the meeting timings to get the answer.

Analysis

• Time Complexity: O(n * log(n))
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Meeting class definition
class Meeting {
public:
   int start, end;
   Meeting(int start, int end) {
       this->start = start;
       this->end = end;
   }
};
*/
bool comp (Meeting* A, Meeting* B) {
   return A->end < B->end;
}
int getMaxMeetings(vector<Meeting*> meetings) {
   sort (meetings.begin(), meetings.end(), comp);
   int maxMeetings = 0, finishTime = 0;
   for (int i = 0; i < meetings.size(); i++) {
       if (meetings[i]->start >= finishTime) {
           maxMeetings++;
           finishTime = meetings[i]->end;
       }
   }
   return maxMeetings;
}

Java

class Solution {
   /* This is the Meeting class definition
   class Meeting {
       public int start;
       public int end;
       public Meeting(int start, int end) {
           this.start = start;
           this.end = end;
       }
   }
   */
   
   int getMaxMeetings(Meeting[] meetings) {
       Arrays.sort (meetings, new Comparator<Meeting> () {
           public int compare (Meeting A, Meeting B) {
               return A.end - B.end;
           }
       });
       int maxMeetings = 0, finishTime = 0;
       for (int i = 0; i < meetings.length; i++) {
           if (meetings[i].start >= finishTime) {
               maxMeetings++;
               finishTime = meetings[i].end;
           }
       }
       return maxMeetings;
   }
}