Maximum meetings in one room

You have one meeting room at your company. There are N meeting needs to take place. Every meeting has a start time and end time along with the meeting title. Your task is to schedule as many meetings as possible in that conference room with no conflicts. 

Example:

Meetings:
A[ Start Time: 1, End Time: 3]
B[ Start Time: 4, End Time: 5]
C[ Start Time: 0, End Time: 7]
D[ Start Time: 6, End Time: 8]
F[ Start Time: 9, End Time: 11]
G[ Start Time: 10, End Time: 12]
Output: A B D F

Meetings:
A[ Start Time: 1, End Time: 3]
B[ Start Time: 2, End Time: 5]
Output: A

Meetings:
A[ Start Time: 2, End Time: 4]
B[ Start Time: 5, End Time: 6]
Output: A B

Approach:

This problem is similar to the activity selection problem.

  1. Sort all the meetings according to their end time.
  2. Select the first meeting and note the end time, call it as current_end.
  3. Now iterate through the rest of the meetings. For each current_meeting
    1. If start time of current_meeting > current_end 
      1. Select current_meeting.
      2. Update current_end = end time of current_meeting.
    2. Else
      1. Ignore the current_meeting.

Time Complexity: O(nlogn)

Complete Code:

Output:

All meetings: [Meeting: A[ Start Time: 1, End Time: 3], Meeting: B[ Start Time: 2, End Time: 5], Meeting: C[ Start Time: 0, End Time: 7], Meeting: D[ Start Time: 6, End Time: 8], Meeting: F[ Start Time: 9, End Time: 11], Meeting: G[ Start Time: 10, End Time: 12]]
Scheduled meetings:
Meeting: A[ Start Time: 1, End Time: 3]
Meeting: D[ Start Time: 6, End Time: 8]
Meeting: F[ Start Time: 9, End Time: 11]

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.