This post is completed by 4 users

  • 0
 Add to List
Medium

493. 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 schedule_end_time.
  3. Now iterate through the rest of the meetings. For each current_meeting
    • If start time of current_meeting >= schedule_end_time 
      • Select current_meeting.
      • Update schedule_end_time = end time of current_meeting.
    • Else
      • Ignore the current_meeting.

Time Complexity: O(nlogn)

 

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]

Related Problems: