There is one meeting room in a firm. There are N meetings in the form of (S[i], F[i]) where S[i] is the start time of meeting i and F[i] is the finish time of meeting i. The task is to find the maximum number of meetings that can be accommodated in the meeting room. Print all meeting numbers
Examples:
Input: s[] = {1, 3, 0, 5, 8, 5}, f[] = {2, 4, 6, 7, 9, 9}
Output: 1 2 4 5
First meeting [1, 2]
Second meeting [3, 4]
Fourth meeting [5, 7]
Fifth meeting [8, 9]Input : s[] = {75250, 50074, 43659, 8931, 11273, 27545, 50879, 77924},
f[] = {112960, 114515, 81825, 93424, 54316, 35533, 73383, 160252 }
Output : 6 7 1
Greedy approach for maximum meetings in one room:
The idea is to solve the problem using the greedy approach which is the same as Activity Selection Problem i.e sort the meetings by their finish time and then start selecting meetings, starting with the one with least end time and then select other meetings such that the start time of the current meeting is greater than the end time of last meeting selected
Follow the given steps to solve the problem using the above approach:
- Sort all pairs(Meetings) in increasing order of each pair’s second number(Finish time).
- Select the first meeting of the sorted pair as the first Meeting in the room and push it into the result vector and set a variable time_limit(say) with the second value(Finishing time) of the first selected meeting.
- Iterate from the second pair to the last pair of the array and if the value of the first element(Starting time of meeting) of the current pair is greater than the previously selected pair’s finish time (time_limit) then select the current pair and update the result vector (push selected meeting number into result vector) and variable time_limit.
- Print the Order of meeting from the result vector.
Below is the implementation of the above approach.
C++
// C++ program to find maximum number of meetings#include <bits/stdc++.h>using namespace std;// Function for finding maximum meeting in one roomvoid maxMeetings(int s[], int f[], int N){ pair<int, int> a[N + 1]; int i; for (i = 0; i < N; i++) { a[i].first = f[i]; a[i].second = i; } // Sorting of meeting according to their finish time. sort(a, a + N); // Time_limit to check whether new // meeting can be conducted or not. int time_limit = a[0].first; // Vector for storing selected meeting. vector<int> m; // Initially select first meeting. m.push_back(a[0].second + 1); // Check for all meeting whether it // can be selected or not. for (i = 1; i < N; i++) { if (s[a[i].second] > time_limit) { // Push selected meeting to vector m.push_back(a[i].second + 1); // update time limit time_limit = a[i].first; } } // Print final selected meetings. for (int i = 0; i < m.size(); i++) { cout << m[i] << " "; }}// Driver's codeint main(){ // Starting time int s[] = { 1, 3, 0, 5, 8, 5 }; // Finish time int f[] = { 2, 4, 6, 7, 9, 9 }; // Number of meetings. int N = sizeof(s) / sizeof(s[0]); // Function call maxMeetings(s, f, N); return 0;} |
Java
// Java program to find maximum number of meetingsimport java.util.*;// Comparator function which can compare// the ending time of the meeting ans// sort the listclass mycomparator implements Comparator<meeting> { @Override public int compare(meeting o1, meeting o2) { if (o1.end < o2.end) { // Return -1 if second object is // bigger than first return -1; } else if (o1.end > o2.end) // Return 1 if second object is // smaller than first return 1; return 0; }}// Custom class for storing starting time,// finishing time and position of meeting.class meeting { int start; int end; int pos; meeting(int start, int end, int pos) { this.start = start; this.end = end; this.pos = pos; }}class GFG { // Function for finding maximum meeting in one room public static void maxMeeting(ArrayList<meeting> al, int s) { // Initialising an arraylist for storing answer ArrayList<Integer> m = new ArrayList<>(); int time_limit = 0; mycomparator mc = new mycomparator(); // Sorting of meeting according to // their finish time. Collections.sort(al, mc); // Initially select first meeting. m.add(al.get(0).pos); // time_limit to check whether new // meeting can be conducted or not. time_limit = al.get(0).end; // Check for all meeting whether it // can be selected or not. for (int i = 1; i < al.size(); i++) { if (al.get(i).start > time_limit) { // Add selected meeting to arraylist m.add(al.get(i).pos); // Update time limit time_limit = al.get(i).end; } } // Print final selected meetings. for (int i = 0; i < m.size(); i++) System.out.print(m.get(i) + 1 + " "); } // Driver's Code public static void main(String[] args) { // Starting time int s[] = { 1, 3, 0, 5, 8, 5 }; // Finish time int f[] = { 2, 4, 6, 7, 9, 9 }; // Defining an arraylist of meet type ArrayList<meeting> meet = new ArrayList<>(); for (int i = 0; i < s.length; i++) // Creating object of meeting // and adding in the list meet.add(new meeting(s[i], f[i], i)); // Function call maxMeeting(meet, meet.size()); }}// This code is contributed by Sarthak Sethi |
Python3
# Python3 program to find maximum number# of meetings# Custom class for storing starting time,# finishing time and position of meeting.class meeting: def __init__(self, start, end, pos): self.start = start self.end = end self.pos = pos# Function for finding maximum# meeting in one roomdef maxMeeting(l, N): # Initialising an arraylist # for storing answer ans = [] # Sorting of meeting according to # their finish time. l.sort(key=lambda x: x.end) # Initially select first meeting ans.append(l[0].pos) # time_limit to check whether new # meeting can be conducted or not. time_limit = l[0].end # Check for all meeting whether it # 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 final selected meetings for i in ans: print(i + 1, end=" ") print()# Driver's codeif __name__ == '__main__': # Starting time s = [1, 3, 0, 5, 8, 5] # Finish time f = [2, 4, 6, 7, 9, 9] # Number of meetings. N = len(s) l = [] for i in range(N): # Creating object of meeting # and adding in the list l.append(meeting(s[i], f[i], i)) # Function call maxMeeting(l, N)# This code is contributed by MuskanKalra1 |
C#
using System;using System.Collections.Generic;public class Pair<T, U> { public Pair() {} public Pair(T first, U second) { this.First = first; this.Second = second; } public T First { get; set; } public U Second { get; set; }};public class GFG { public static int cmp(Pair<int, int> a, Pair<int, int> b) { if (a.Second < b.Second) { // Return -1 if second object is // bigger than first return -1; } else if (a.Second > b.Second) // Return 1 if second object is // smaller than first return 1; return 0; } // Function for finding maximum meeting in one room public static void maxMeetings(int[] s, int[] f, int N) { List<Pair<int, int> > a = new List<Pair<int, int> >(); int i; for (i = 0; i < N; i++) { Pair<int, int> abc = new Pair<int, int>(f[i], i); a.Add(abc); } // Sorting of meeting according to their finish // time. a.Sort(cmp); // Time_limit to check whether new // meeting can be conducted or not. int time_limit = a[0].First; // Vector for storing selected meeting. List<int> m = new List<int>(); // Initially select first meeting. m.Add(a[0].Second + 1); // Check for all meeting whether it // can be selected or not. for (i = 1; i < N; i++) { if (s[a[i].Second] > time_limit) { // Push selected meeting to vector m.Add(a[i].Second + 1); // update time limit time_limit = a[i].First; } } // Print final selected meetings. for (int j = 0; j < m.Count; j++) { Console.Write(m[j]); Console.Write(" "); } } // Driver's code static public void Main() { // Starting time int[] s = { 1, 3, 0, 5, 8, 5 }; // Finish time int[] f = { 2, 4, 6, 7, 9, 9 }; // Number of meetings. int N = s.Length; // Function call maxMeetings(s, f, N); }}// This code is contributed by contributed by akashish__ |
Javascript
// JavaScript program to find maximum number of meetings// Function for finding maximum meeting in one roomfunction maxMeetings(s, f, n){ //Make an Array : aCollectiveArray like [[index, startTime, endTime]] //index will be stored as i + 1, to start indices from 1. var aCollectiveArray = []; for(var i=0; i<s.length; i++){ var aNew = []; aNew.push(i + 1); aNew.push(s[i]); aNew.push(f[i]); aCollectiveArray.push(aNew); } //array sorted based on end Time aCollectiveArray.sort((a,b) => a[2] - b[2]); //endTime is at 2nd index of subarray inside aCollectiveArray var endTime = aCollectiveArray[0][2]; //result will contain the indices of meetings var result = []; //first meeting will be bydefault push as array is already sorted result.push(aCollectiveArray[0][0]); //will compare if next startTime > prev endTime for(var k=1; k<aCollectiveArray.length; k++){ var startTime = aCollectiveArray[k][1]; if(startTime > endTime){ result.push(aCollectiveArray[k][0]); endTime = aCollectiveArray[k][2] } } //If we need to return indices then will return : result //or else if we need to return number of meetings then will return result.length return result;}// Driver code// Starting timelet s = [ 1, 3, 0, 5, 8, 5 ];// Finish timelet f = [ 2, 4, 6, 7, 9, 9 ];// Number of meetings.let n = s.length;// Function callmaxMeetings(s, f, n);//This code is contributed by Ankit Kumar. |
Output:
1 2 4 5
Time Complexity: O(N log N)
Auxiliary Space: O(N) for creating a vector of pairs that is approximately equal to O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
