## Greedy Approach

The greedy approach is like making choices one step at a time and always picking the best at the moment with the hope that it will lead to an overall optimal solution.

- The basic idea is to use
**greedy approach** to choose the meetings such that they can be conducted in one room without any scheduling conflicts. The procedure is very similar to the activity selection problem.

- Create a structure named â€śmeetâ€ť, with three entities, namely: meeting number, start time and end time.

- Create the struct array MEETING of size N and initialize it with the given start, end times, and 1-based indexes.

- Maintain a vector â€śresultâ€ť to store the meeting number of the meetings scheduled in one room.

- Declare a variable â€śprev_endâ€ť to store the ending time of the previous meeting selected.

- Sort the array MEETING in increasing order of the end times.

- The first meeting of the MEETING array is selected, and its meeting number of pushed in the result vector. Update the prev_end as MEETING[0].end

- Traverse the entire MEETING array and keep selecting the meetings whose start time is strictly greater than prev_end.

- Return the result vector.

Itâ€™s interesting to know why the __greedy algorithm__ works in this case and gives an optimal solution.

### Why greedy approach works?

Our goal is to maximize the number of meetings in one room. While choosing the meetings greedily with a minimum ending time first, we are left with more time to schedule more meetings in one room. Hence, as a result, we are able to allocate maximum meetings in one room.

__Dry Run__

Letâ€™s see the dry run of the greedy approach discussed to gain more clarity.

**N** = 6

**Start[]** = {1, 3, 0, 5, 8, 5}

**End[]** = {2, 4, 6, 7, 9, 9}

- Create the MEETING array for the given input.

The MEETING array looks like-

`[[1, 1, 2], [2, 3, 4], [3, 0, 6], [4, 5, 7], [5, 8, 9], [6,5,9]]`

2. Sort the array in increasing order of end time. If two meets have equal end times, then sort them according to their occurrence in the input.

MEETING array after sorting -

`[[1, 1, 2], [2, 3, 4], [3, 0, 6], [4, 5, 7], [5, 8, 9], [6,5,9]]`

3. For index=1, add this meeting number to the result vector. Update the prev_end = 2.

4. For index=2, start time = 3 and prev_end = 2. Since, start > prev_end, so add its meeting number to result vector and update prev_end=4.

5. For index=3, start time = 0 and prev_end = 4. Since, start < prev_end, this meeting cant be allocated to the same room.

6. For index=4, start time = 5 and prev_end =4. Since start > prev_end, so add its meeting number to the result vector and update prev_end=7.

7. For index=5, start time = 8 and prev_end = 7. Since, start > prev_end, so add its meeting number to result vector and update prev_end=9.

8. For index=6, start time = 5 and prev_end = 2. Since, start < prev_end, this meeting cant be allocated to the same room.

9. Return the result vector.

We will see the implementation and complexity analysis of this approach in the next section.

## Code Implementations

### Implementation in C++

### C++

`/*C++ code to find the maximum meetings in one room using greedy approach*/`

#include <bits/stdc++.h>

using namespace std;

struct meet

{

int meetingID;

int startTime;

int endTime;

};

bool compare(struct meet a, struct meet b)

{

if (a.endTime == b.endTime)

{

return a.meetingID < b.meetingID;

}

else

{

return a.endTime < b.endTime;

}

}

vector<int> maximumMeetings(vector<int> &start, vector<int> &end)

{

int n = start.size();

// Creating meeting array of size N

struct meet meeting[n];

for (int i = 0; i < n; i++)

{

meeting[i].meetingID = i + 1;

meeting[i].startTime = start[i];

meeting[i].endTime = end[i];

}

// Sorting the meeting array in increasing order of end time using customized comparator.

sort(meeting, meeting + n, compare);

vector<int> result;

// Taking the first meeting of sorted array as our first meeting.

result.push_back(meeting[0].meetingID);

int currentTime = meeting[0].endTime;

for (int i = 1; i < n; i++)

{

// If startTime of current meeting is greater than our currentTime.

// Then we will perform this meeting and update currentTime with endTime of the meeting.

if (meeting[i].startTime > currentTime)

{

result.push_back(meeting[i].meetingID);

currentTime = meeting[i].endTime;

}

}

return result;

}

int main()

{

vector<int> start, end;

start = {1, 3, 0, 5, 8, 5};

end = {2, 4, 6, 7, 9, 9};

vector<int> result = maximumMeetings(start, end);

cout << "The meetings that can be scheduled in one room such that number of meetings is maximum are:\n";

for (int a : result)

{

cout << a << " ";

}

}

**Output**

### Implementation in Java

### java

`// Java program to find maximum number of meetings in one room`

import java.util.*;

/*The comparator function compares the meeting's finish time and sorts the results.*/

class mycomparator implements Comparator<meeting>

{

@Override

public int compare(meeting obj1, meeting obj2)

{

if (obj1.endOfMeeting < obj2.endOfMeeting)

{

// If the second item is larger than the first, return -1.

return -1;

}

else if (obj1.endOfMeeting > obj2.endOfMeeting)

// If the second item is smaller than the first, return 1.

return 1;

return 0;

}

}

/*Custom class for storing meeting start and end times, as well as meeting location.*/

class meeting

{

int startOfMeeting;

int endOfMeeting;

int posOfMeeting;

meeting(int startOfMeeting, int endOfMeeting, int posOfMeeting)

{

this.startOfMeeting = startOfMeeting;

this.endOfMeeting = endOfMeeting;

this.posOfMeeting = posOfMeeting;

}

}

class Main{

// Finding the most meetings in a single room is a function.

public static void maximumMeeting(ArrayList<meeting> alVar, int s)

{

// Setting up an arraylist to store the response

ArrayList<Integer> myAl = new ArrayList<>();

int time_limit = 0;

mycomparator mcomp = new mycomparator();

// Meetings are arranged in order of their completion time.

Collections.sort(alVar, mcomp);

// To begin, choose the first meeting.

myAl.add(alVar.get(0).posOfMeeting);

// To see if a new meeting may be held, use the time_limit parameter.

time_limit = alVar.get(0).endOfMeeting;

// Check whether all meetings can be selected or not.

for(int i = 1; i < alVar.size(); i++)

{

if (alVar.get(i).startOfMeeting > time_limit)

{

// Add a meeting to the arraylist that you've chosen.

myAl.add(alVar.get(i).posOfMeeting);

// Time limit updates

time_limit = alVar.get(i).endOfMeeting;

}

}

// Print the final list of meetings.

for(int i = 0; i < myAl.size(); i++)

System.out.print(myAl.get(i) + 1 + " ");

}

public static void main (String[] args)

{

// Starting_time

int start[] = { 1, 3, 0, 5, 8, 5 };

// End_time

int end[] = { 2, 4, 6, 7, 9, 9 };

// Creating a meet type arraylist

ArrayList<meeting> meetAl = new ArrayList<>();

for(int i = 0; i < start.length; i++)

// Creating a meeting object and adding it to the list

meetAl.add(new meeting(start[i], end[i], i));

// Function_Call

System.out.println("The meetings that can be scheduled in one room such that number of meetings is maximum are:");

maximumMeeting(meetAl, meetAl.size());

}

}

**Output**

### Implementation in Python

### Python

`# Python program to find maximum number of meetings in one room`

# For storing the start time, create a custom class.

# Time and location of the meeting's conclusion.

class meeting:

def __init__(self, start, end, pos):

self.start = start

self.end = end

self.pos = pos

# Function for finding maximum meeting in one room

def maxMeeting(l, n):

# Setting up an arraylist to store the response

ans = []

# Meetings are arranged in order of their completion time.

l.sort(key = lambda x: x.end)

# To begin, choose the first meeting.

ans.append(l[0].pos)

# To see if a new meeting may be held, use the time_limit parameter.

time_limit = l[0].end

# Check whether all meetings can be selected or not.

for i in range(1, n):

if l[i].start > time_limit:

ans.append(l[i].pos)

time_limit = l[i].end

# Print the final list of meetings.

for i in ans:

print(i + 1, end = " ")

print()

if __name__ == '__main__':

# Starting_time

start = [ 1, 3, 0, 5, 8, 5 ]

# End_time

end = [ 2, 4, 6, 7, 9, 9 ]

# NumberOfMeetings

n = len(start)

l = []

for i in range(n):

# Creating a meeting object and adding it to the list

l.append(meeting(start[i], end[i], i))

print("The meetings that can be scheduled in one room such that number of meetings is maximum are:")

# FunctionCall

maxMeeting(l, n)

**Output**

### Complexity Analysis

**Time Complexity**

O(N * logN), where N is the number of meetings. In the worst case, we are traversing the input arrays once which takes O(N) time and we are sorting the MEETING array of size N which takes O(N * log(N)) time. Thus the final time complexity is O(N) + O(N * log(N)) = O(N * log(N)).

**Space Complexity **

O(N), where N is the number of meetings.

Since we create a MEETING array of size N, hence the space complexity is O(N).

Check out this problem - __Maximum Product Subarray__

## Frequently Asked Questions

**What is find maximum meetings in one room problem?**

In a company, there is just one conference room. There are N meetings in the form of (S[i], F[i]), where S[i] is the meeting I start time and F[i] is the meeting I finish time. The goal is to identify the greatest number of meetings that the meeting space can hold. All meeting numbers should be printed.

**What are the benefits of the greedy approach?**

The greedy approach is easy to implement. Typically have less time complexity. Greedy algorithms can be used for optimization purposes or finding close to optimization in case of Hard problems.

**What is the first step to solving the find maximum meetings in one room problem when we are using the greedy approach?**

The first step is to sort all pairings (Meetings) by the second number (Finish time) of each pair in ascending order.

## Conclusion

In this article, we saw the greedy approach of finding the maximum number of meetings in one room.

Some of the problems based on a similar concept that you can try are-

Refer to our guided paths on Coding Ninjas Studio to learn more about Data Structures and Algorithms, Competitive Programming, etc. Enroll in our courses and refer to the mock test and problems available; look at the Top 150 Interview Puzzles, interview experiences, and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Coding!