Minimum chairs for group timings
Given an integer N representing the total size of groups S, their entry T1 and exit timings T2. This means that group number i will come at T1[i], leave at T2[i], and have a variable size in group S[i]. the task is to find the minimum number of chairs to be bought so that every customer has a chair to sit in.
Examples:
Input: N = 5, T1 = {7, 18, 16, 14, 16}, T2 = {18, 21, 23, 16, 22}, S = {8, 11, 20, 4, 7}
Output: 46
Explanation: Between time [18, 18], Groups 1, 2, 3, and 5 will be concurrent of size 46.Input: N = 4, T1 = {20, 9, 16, 2}, T2 = {24, 10, 23, 6}, S = {8, 3, 20, 10}
Output: 28
Explanation: Between time [20, 23], Groups 1 and 3 will be concurrent with size 28.Input: N = 4, T1 = {6, 9, 1, 6}, T2 = {11, 18, 18, 8}, S = {5, 19, 5, 14}
Output: 29
Explanation: Between time [9, 11], Groups 1, 2, and 3 will be concurrent of size 29.
Intuition:
The idea is to use the concept of prefix sum to compute the number of customers at each time index. By incrementing the start time index and end time index in the range vector, it effectively creates a “prefix sum array” that stores the total number of customers at each time index. The second loop then utilizes another prefix sum technique to compute the maximum number of customers at any given time. The maximum number of customers is then returned as the minimum number of chairs required to seat all.
Approach: This can be solved with the following idea:
The approach used in this code is to create a vector called “range” of size 1e6 (10^6) and initialize all the values to zero. Then, for each group, the start time index and end time index in the “range” vector are incremented by the corresponding number of customers. This is done using a loop from 0 to N-1, where N is the number of groups. The start time index is represented by T1[i] and the end time index by T2[i] + 1 since the customers should leave after the deadline time.
After the first loop, the range vector now stores the total number of customers at each time index. Then, a second loop is used to compute the maximum number of customers at any given time by keeping a running total of the customers from the start of the day to the current time index.
Below is the implementation of the above approach:
C++14
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Minimum number of chairs needed int minChairsToSeat( int & N, vector< int >& T1, vector< int >& T2, vector< int >& S) { // Create a range vector< int > range(1e6, 0); int maxVal = 0; // Store the range in given vector for ( int i = 0; i < N; i++) { range[T1[i]] += S[i]; range[T2[i] + 1] -= S[i]; } for ( int i = 1; i <= 1e5; i++) { range[i] += range[i - 1]; maxVal = max(maxVal, range[i]); } return maxVal; } // Driver's code int main() { int N = 5; vector< int > T1 = { 7, 18, 16, 14, 16 }; vector< int > T2 = { 18, 21, 23, 16, 22 }; vector< int > S = { 8, 11, 20, 4, 7 }; // Function call cout << minChairsToSeat(N, T1, T2, S); return 0; } |
Java
// Java code for the above approach: import java.util.*; import java.lang.*; import java.io.*; class GFG { // Minimum number of chairs needed static int minChairsToSeat( int N, int [] T1, int [] T2, int [] S) { // Create a range int [] range = new int [( int ) 1e6]; int maxVal = 0 ; // Store the range in given vector for ( int i = 0 ; i < N; i++) { range[T1[i]] += S[i]; range[T2[i] + 1 ] -= S[i]; } for ( int i = 1 ; i <= 1e5; i++) { range[i] += range[i - 1 ]; maxVal = Math.max(maxVal, range[i]); } return maxVal; } // Driver's code public static void main(String[] args) { int N = 5 ; int [] T1 = { 7 , 18 , 16 , 14 , 16 }; int [] T2 = { 18 , 21 , 23 , 16 , 22 }; int [] S = { 8 , 11 , 20 , 4 , 7 }; // Function call System.out.println(minChairsToSeat(N, T1, T2, S)); } } // This code is contributed by Tapesh(tapeshdua420) |
Python3
# Python code for the above approach: def minChairsToSeat(N, T1, T2, S): # Create a range range_ = [ 0 ] * ( 10 * * 6 ) maxVal = 0 # Store the range in the given list for i in range (N): range_[T1[i]] + = S[i] range_[T2[i] + 1 ] - = S[i] for i in range ( 1 , 10 * * 5 + 1 ): range_[i] + = range_[i - 1 ] maxVal = max (maxVal, range_[i]) return maxVal # Driver's code if __name__ = = '__main__' : N = 5 T1 = [ 7 , 18 , 16 , 14 , 16 ] T2 = [ 18 , 21 , 23 , 16 , 22 ] S = [ 8 , 11 , 20 , 4 , 7 ] # Function call print (minChairsToSeat(N, T1, T2, S)) |
C#
// C# code for the above approach using System; using System.Collections.Generic; public class GFG { // Minimum number of chairs needed static int MinChairsToSeat( ref int N, List< int > T1, List< int > T2, List< int > S) { // Create a range List< int > range = new List< int >(( int )1e6); int maxVal = 0; // Initialize the range for ( int i = 0; i < ( int )1e6; i++) { range.Add(0); } // Store the range in the given list for ( int i = 0; i < N; i++) { range[T1[i]] += S[i]; range[T2[i] + 1] -= S[i]; } for ( int i = 1; i <= ( int )1e5; i++) { range[i] += range[i - 1]; maxVal = Math.Max(maxVal, range[i]); } return maxVal; } // Driver's code static void Main( string [] args) { int N = 5; List< int > T1 = new List< int >{ 7, 18, 16, 14, 16 }; List< int > T2 = new List< int >{ 18, 21, 23, 16, 22 }; List< int > S = new List< int >{ 8, 11, 20, 4, 7 }; // Function call Console.WriteLine( MinChairsToSeat( ref N, T1, T2, S)); } } // This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript code for the above approach: // Minimum number of chairs needed function minChairsToSeat(N, T1, T2, S) { // Create a range const range = new Array(1e6).fill(0); let maxVal = 0; // Store the range in the given array for (let i = 0; i < N; i++) { range[T1[i]] += S[i]; range[T2[i] + 1] -= S[i]; } for (let i = 1; i <= 1e5; i++) { range[i] += range[i - 1]; maxVal = Math.max(maxVal, range[i]); } return maxVal; } // Driver's code const N = 5; const T1 = [7, 18, 16, 14, 16]; const T2 = [18, 21, 23, 16, 22]; const S = [8, 11, 20, 4, 7]; // Function call console.log(minChairsToSeat(N, T1, T2, S)); |
46
Time Complexity: O(N+T)
Auxiliary Space: O(T)