Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Expected Output - 
3.
Greedy Approach
3.1.
Why greedy approach works?  
4.
Code Implementations
4.1.
Implementation in C++
4.2.
C++
4.3.
Implementation in Java
4.4.
java
4.5.
Implementation in Python
4.6.
Python
4.7.
Complexity Analysis
4.7.1.
Time Complexity
4.7.2.
Space Complexity 
5.
Frequently Asked Questions
5.1.
What is find maximum meetings in one room problem?
5.2.
What are the benefits of the greedy approach?
5.3.
What is the first step to solving the find maximum meetings in one room problem when we are using the greedy approach?
6.
Conclusion
Last Updated: Jun 11, 2024
Medium

Find Maximum Meetings in One Room

Author Yukti Kumari
4 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

In this article, we will solve the problem of N meeting in one room. Firstly, we will understand the problem statement and then note the thought process to build up the solution.

n meeting in one room

Let’s get started with the problem statement.

Problem Statement

You are given the schedule of N meetings with their start time Start[i] and end time End[i]. But you have only 1 meeting room. So, you need to find the meeting numbers you can organize in the given room, such that the number of meetings organized is maximum.

Note: The start time of one chosen meeting can’t be equal to the end time of the other chosen meeting. Also, for the same end time, a meeting with a smaller index is preferred.

Print the meeting numbers (Consider 1-based indexing) you organized in the given room, in the order in which you organized them such that the number of meetings is maximum.

We will first take an example to understand what is required to be done.

Example -

N = 6

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

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

 

Meetings in One Room

 

Expected Output

1 2 4 5

Maximum 4 meetings can be scheduled in one room. Meeting number 1 from 1 to 2, Meeting number 2 from 3 to 4, Meeting number 4 from 5 to 7, and Meeting number 5 from 8 to 9.

Recommended: Try the Problem of maximum meeting yourself before moving on to the solution.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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}

  1. 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++

/*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

output

Implementation in Java

  • 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

output

Implementation in Python

  • 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

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!

Previous article
Queue Reconstruction by Height
Next article
Finding Kth Largest Number in a Given Array of Large Numbers
Live masterclass