There is only one room which is holding N meetings that are given as intervals of the form (start[i], end[i], people[i]) where start[i] is the starting time of the ith meeting, end[i] is the ending time of the ith meeting, people[i] is the number of people who can attend the ith meeting. At any point of time, the room can be occupied by only one meeting i.e., If two meetings have overlapping intervals then only one of them can be picked. The task is to find the maximum number of people who can attend the meeting.
Examples:
Input: Meetings = { {5, 8, 3}, {1, 4, 5}, {7, 10, 2} }
Outputs: 8
Explanation: The optimal meetings are {1, 4, 5} and {5, 8, 3}.
So, 5+3 = 8 is the maximum number of people.Input: Meetings = { {1, 5, 20}, {3, 8, 50}.{6, 10, 70} }
Output: 90
Explanation: The optimal meetings are {1, 5, 20}, {6, 10, 70}.
So, 20 + 70 = 90 is the maximum number of people.
Approach: The problem can be solved using dynamic programming based on the below observation:
Process the meetings by sorting in a non-decreasing order of the end time as it is optimal to first process the meeting that gets over the earliest. We can use Dynamic Programming to solve this problem.
Create a dp[] array where dp[i] = maximum number of people who can attend the meeting till the ith meeting. At any particular point i, check if the ith meeting overlaps with the (i-1)th meeting.
- If there is no overlap dp[i] = dp[i-1] + people[i] ( maximum number of people possible till i-1 + people[i])
- Otherwise, dp[i] = max( dp[i-1], dp[j] + people[i] ) (maximum number of people possible till i-1 or maximum number of people possible till some jth meeting which is nearest non-overlapping meeting with i where j < i.
We can use binary search to find j.
Follow the steps mentioned below to implement the idea:
- Sort the meetings according to the end time of the meetings.
- Start iterating from the start of the sorted array of meetings.
- For each index follow the above mentioned relation.
- If the adjacent intervals overlap, use binary search in the prefix to find the j.
- Return the value stored at dp[N-1] as the required answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum number of peopleint maxPeople(vector<vector<int> >& data, int n){ // Sorting the intervals according to // the end time in non decreasing order sort(data.begin(), data.end(), [&](vector<int> a, vector<int> b) { if (a[1] == b[1]) return a[0] < b[0]; else return a[1] < b[1]; }); vector<int> dp(n, 0); dp[0] = data[0][2]; // Need a map to store the highest possible value // for same end timed intervals map<int, int> mp; // First interval is assumed to be taken at first // the highest value with its ending time is dp[0] mp[data[0][1]] = dp[0]; for (int i = 1; i < n; i++) { int curstart = data[i][0]; int curend = data[i][1]; // If the ith interval overlaps with // the (i-1)th interval if (curstart <= data[i - 1][1]) { // Binary search for an interval that has // its ending time just lesser than // the starting time of the ith interval int left = 0; int right = i; int var = data[i][0]; while (left < right) { int mid = left + (right - left) / 2; if (data[mid][1] < var) left = mid; else right = mid - 1; } // We have two choice either we don't pick // the ith interval then dp[i-1] or we pick // the ith interval then dp[left]+ith value. // We use mp[data[left][1]] instead of // dp[left] since our map stores the maximum of // the dp values that end with a given end time. dp[i] = max(dp[i - 1], mp[data[left][1]] + data[i][2]); // Update the map with max of current dp // value and mp[data[i][1]] accounting for an // interval that may have higher dp value ending // with the same end time as the ith interval. mp[data[i][1]] = max(dp[i], mp[data[i][1]]); } else { dp[i] = dp[i - 1] + data[i][2]; mp[data[i][1]] = max(mp[data[i][1]], dp[i]); } } // Return the required answer return dp[n - 1];}// Driver codeint main(){ vector<vector<int> > Meetings = { { 5, 8, 3 }, { 1, 4, 5 }, { 7, 10, 2 } }; int N = Meetings.size(); // Function call cout << maxPeople(Meetings, N); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;// sorting a list of listclass ListComparator<T extends Comparable<T> > implements Comparator<List<T> > { @Override public int compare(List<T> o1, List<T> o2) { for (int i = 0; i < Math.min(o1.size(), o2.size()); i++) { int c = o1.get(i).compareTo(o2.get(i)); if (c != 0) { return c; } } return Integer.compare(o1.size(), o2.size()); }}class GFG { // Function to find the maximum number of people public static int maxPeople(List<List<Integer> > data, int n) { // Sorting the intervals according to // the end time in non decreasing order Collections.sort(data, new ListComparator<>()); List<Integer> dp = new ArrayList<Integer>(); for (int i = 0; i < n; i++) { dp.add(0); } dp.set(0, data.get(0).get(2)); // Need a map to store the highest possible value // for same end timed intervals Map<Integer, Integer> mp = new HashMap<Integer, Integer>(); for (int i = 0; i < 15; i++) { mp.put(i, 0); } // First interval is assumed to be taken at first // the highest value with its ending time is dp[0] mp.put(data.get(0).get(1), dp.get(0)); for (int i = 1; i < n; i++) { int curstart = data.get(i).get(0); int curend = data.get(i).get(1); // If the ith interval overlaps with // the (i-1)th interval if (curstart <= data.get(i - 1).get(1)) { // Binary search for an interval that has // its ending time just lesser than // the starting time of the ith interval int left = 0; int right = i; int var = data.get(i).get(0); while (left < right) { int mid = left + (right - left) / 2; if (data.get(mid).get(1) < var) left = mid; else right = mid - 1; } // We have two choice either we don't pick // the ith interval then dp[i-1] or we pick // the ith interval then dp[left]+ith value. // We use mp[data[left][1]] instead of // dp[left] since our map stores the maximum // of the dp values that end with a given // end time. dp.set(i, Math.max( dp.get(i - 1), mp.get(data.get(left).get(1)) + data.get(i).get(2))); // Update the map with max of current dp // value and mp[data[i][1]] accounting for // an interval that may have higher dp value // ending with the same end time as the ith // interval. mp.put( data.get(i).get(1), Math.max(dp.get(i), mp.get(data.get(i).get(1)))); } else { dp.set(i, dp.get(i - 1) + data.get(i).get(2)); mp.put(data.get(i).get(1), Math.max(mp.get(data.get(i).get(1)), dp.get(i))); } } // Return the required answer return dp.get(n - 1); } public static void main(String[] args) { List<List<Integer> > Meetings = new ArrayList<>(); List<Integer> a = new ArrayList<Integer>(); a.add(5); a.add(8); a.add(3); Meetings.add(a); List<Integer> b = new ArrayList<Integer>(); b.add(1); b.add(4); b.add(5); Meetings.add(b); List<Integer> c = new ArrayList<Integer>(); c.add(7); c.add(10); c.add(2); Meetings.add(c); int N = Meetings.size(); // Function call System.out.println(maxPeople(Meetings, N)); }}// This code is contributed by akashish__ |
Python3
# Python code to implement the approach# Function to find the maximum number of peopledef maxPeople(data,n): # Sorting the intervals according to # the end time in non decreasing order data.sort(key=lambda a:a[1]) dp=[0]*n dp[0]=data[0][2] # Need a map to store the highest possible value # for same end timed intervals mp=[0]*15 # First interval is assumed to be taken at first # the highest value with its ending time is dp[0] mp[data[0][1]]=dp[0] for i in range(1,n): curstart=data[i][0] curend=data[i][1] # If the ith interval overlaps with # the (i-1)th interval if(curstart<=data[i-1][1]): # Binary search for an interval that has # its ending time just lesser than # the starting time of the ith interval left=0 right=i var=data[i][0] while(left<right): mid=left+(right-left)//2 if(data[mid][1]<var): left=mid else: right=mid-1 # We have two choice either we don't pick # the ith interval then dp[i-1] or we pick # the ith interval then dp[left]+ith value. # We use mp[data[left][1]] instead of # dp[left] since our map stores the maximum of # the dp values that end with a given end time. dp[i]=max(dp[i-1],mp[data[left][1]]+data[i][2]) # Update the map with max of current dp # value and mp[data[i][1]] accounting for an # interval that may have higher dp value ending # with the same end time as the ith interval. mp[data[i][1]]=max(dp[i],mp[data[i][1]]) else: dp[i]=dp[i-1]+data[i][2] mp[data[i][1]]=max(mp[data[i][1]],dp[i]) # Return the required answer return dp[n-1] # Driver codeMeetings=[[5,8,3],[1,4,5],[7,10,2]]N=len(Meetings)# Function callprint(maxPeople(Meetings,N))# This code is contributed by Pushpesh raj. |
C#
using System;using System.Collections.Generic;public class GFG { public static int cmp(List<int> a, List<int> b) { if (a[1] == b[1]) { if (a[0] < b[0]) return -1; } else { if (a[1] < b[1]) return -1; } return 1; } // Function to find the maximum number of people public static int maxPeople(List<List<int> > data, int n) { // Sorting the intervals according to // the end time in non decreasing order data.Sort(cmp); List<int> dp = new List<int>(); for (int i = 0; i < n; i++) { dp.Add(0); } dp[0] = data[0][2]; // Need a map to store the highest possible value // for same end timed intervals Dictionary<int, int> mp = new Dictionary<int, int>(); for (int i = 0; i < 15; i++) { mp.Add(i, 0); } // First interval is assumed to be taken at first // the highest value with its ending time is dp[0] mp[data[0][1]] = dp[0]; for (int i = 1; i < n; i++) { int curstart = data[i][0]; int curend = data[i][1]; // If the ith interval overlaps with // the (i-1)th interval if (curstart <= data[i - 1][1]) { // Binary search for an interval that has // its ending time just lesser than // the starting time of the ith interval int left = 0; int right = i; int var = data[i][0]; while (left < right) { int mid = left + (right - left) / 2; if (data[mid][1] < var) left = mid; else right = mid - 1; } // We have two choice either we don't pick // the ith interval then dp[i-1] or we pick // the ith interval then dp[left]+ith value. // We use mp[data[left][1]] instead of // dp[left] since our map stores the maximum // of the dp values that end with a given // end time. dp[i] = Math.Max(dp[i - 1], mp[data[left][1]] + data[i][2]); // Update the map with max of current dp // value and mp[data[i][1]] accounting for // an interval that may have higher dp value // ending with the same end time as the ith // interval. mp[data[i][1]] = Math.Max(dp[i], mp[data[i][1]]); } else { dp[i] = dp[i - 1] + data[i][2]; mp[data[i][1]] = Math.Max(mp[data[i][1]], dp[i]); } } // Return the required answer return dp[n - 1]; } static public void Main() { List<List<int> > Meetings = new List<List<int> >(); Meetings.Add(new List<int>() { 5, 8, 3 }); Meetings.Add(new List<int>() { 1, 4, 5 }); Meetings.Add(new List<int>() { 7, 10, 2 }); int N = Meetings.Count; // Function call Console.WriteLine(maxPeople(Meetings, N)); }}// This code is contributed by akashish__ |
Javascript
function cmp(a, b) { if (a[1] == b[1]) { if (a[0] < b[0]) return -1; } else { if (a[1] < b[1]) return -1; } return 1;}// Function to find the maximum number of peoplefunction maxPeople(data, n) { // Sorting the intervals according to // the end time in non decreasing order data.sort(cmp); let dp = []; for (let i = 0; i < n; i++) { dp.push(0); } dp[0] = data[0][2]; // Need a map to store the highest possible value // for same end timed intervals let mp = new Map(); for (let i = 0; i < 15; i++) { mp.set(i, 0); } // First interval is assumed to be taken at first // the highest value with its ending time is dp[0] mp[data[0][1]] = dp[0]; for (let i = 1; i < n; i++) { let curstart = data[i][0]; let curend = data[i][1]; // If the ith interval overlaps with // the (i-1)th interval if (curstart <= data[i - 1][1]) { // Binary search for an interval that has // its ending time just lesser than // the starting time of the ith interval let left = 0; let right = i; let vari = data[i][0]; while (left < right) { let mid = left + (right - left) / 2; if (data[mid][1] < vari) left = mid; else right = mid - 1; } // We have two choice either we don't pick // the ith interval then dp[i-1] or we pick // the ith interval then dp[left]+ith value. // We use mp[data[left][1]] instead of // dp[left] since our map stores the maximum // of the dp values that end with a given // end time. dp[i] = Math.max(dp[i - 1], mp.get(data[left][1]) + data[i][2]); // Update the map with max of current dp // value and mp[data[i][1]] accounting for // an interval that may have higher dp value // ending with the same end time as the ith // interval. mp.set(data[i][1], Math.max(dp[i], mp.get(data[i][1]))); } else { dp[i] = dp[i - 1] + data[i][2]; mp.set(data[i][1], Math.max(mp.get(data[i][1]), dp[i])); } } // Return the required answer return dp[n - 1];}let Meetings = [[5, 8, 3], [1, 4, 5], [7, 10, 2]];let N = Meetings.length;// Function callconsole.log(maxPeople(Meetings, N));// This code is contributed by akashish__ |
Output
8
Time Complexity: O(N * logN)
Auxiliary Space: 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!
