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++ 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;
}

46

Time Complexity: O(N+T)
Auxiliary Space: O(T)