Rooms

Harsh is thinking of starting his own business. He has decided to start with the hotel business. He has been given a list that contains the arrival time and the duration of stay of each guest at his hotel. He can give 1 room to only 1 guest. Since he does not want to disappoint his guests he wants to find the minimum number of rooms he needs to build so that he could accommodate all the guests. Help him in finding this answer.

Example:

Input:  n = 3, a = [1,2,3], x = [3,3,3]
Output: 3

Approach

C++

#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b)
{
    if (a.first == b.first)
        return a.second < b.second;
    return a.first < b.first;
}

int rooms(int n, int a[], int x[])
{
    int d[n];
    for (int i = 0; i < n; i++)
    {
        d[i] = a[i] + x[i];
    }
    vector<pair<int, int>> v;
    for (int i = 0; i < n; i++)
        v.push_back({a[i], d[i]});
    sort(v.begin(), v.end(), cmp);
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 0; i < n; i++)
    {
        if (q.empty())
            q.push(v[i].second);
        else
        {
            int y = q.top();
            if (y <= v[i].first)
                q.pop();
            q.push(v[i].second);
        }
    }
    return q.size();
}
int main()
{

    int n = 3;

    int a[n] = {1, 2, 3}, x[n] = {3, 3, 3};

    cout << rooms(n, a, x) << "\n";

    return 0;
}