Greedy: Maximum meetings in one room

Problem Statement:

You have one meeting room in your company. There are multiple meetings taking place.

Every meeting has a start and end time along with the meeting title.

You need to schedule as many meetings as possible without conflicts.

Example

start time = [1,4,0,6,9,10]
End time = [3,5,7,8,11,12]

Output:
The maximum meetings that can occur are 4.

They are:

A[1,3], B[4,5], D[6,8], E[9,11]

Solution

The solution is very similar to activity selection problem.

We will use greedy approach to solve this problem. i.e we need to adjust all the meetings in such a way that the maximum meeting needs to take place in the single room.

We use below steps to arrive at the solution:

1. Sort all the meeting according to their end time.

2. Now select the first meeting and its end time.

3. Now iterate through the rest of the meeting, for each meeting,
   		1. If the start time is > previous meeting then 
   			a. increment counter by 1
   			b. previous meeting end = end time of current meeting.

   		2. else ignore the current meeting

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>

using namespace std;

struct meeting 
{
    int start;
    int end;
    int pos;
};

bool sort_helper(struct meeting m1, meeting m2)
{
    return (m1.end < m2.end);
}
 
void get_max_meeting(int start[], int end[], int n)
{
    struct meeting meet[n];

    for (int i = 0; i < n; i++)
    {
        meet[i].start = start[i];
         
        meet[i].end = end[i];
         
        meet[i].pos = i + 1;
    }
 
    sort(meet, meet + n, sort_helper);
 
    vector<int> selected_meetings;
 
    selected_meetings.push_back(meet[0].pos);
 
    int time_limit = meet[0].end;
 
    for (int i = 1; i < n; i++) 
    {
        if (meet[i].start >= time_limit)
        {
            selected_meetings.push_back(meet[i].pos);
             
            time_limit = meet[i].end;
        }
    }
 
    for (int i = 0; i < selected_meetings.size(); i++) 
    {
        cout << selected_meetings[i] << " ";
    }
}
 
int main()
{
    int start[] = { 1, 3, 0, 5, 8, 5 };
     
    int end[] = { 2, 4, 6, 7, 9, 9 };
     
    int n = sizeof(start) / sizeof(start[0]);
 
    get_max_meeting(start, end, n);
 
    return 0;
}

Output:

1 2 4 5