Room Allocation

There is a large hotel, and n customers will arrive soon. Each customer wants to have a single room.

You know each customer's arrival and departure day. Two customers can stay in the same room if the departure day of the first customer is earlier than the arrival day of the second customer.

What is the minimum number of rooms that are needed to accommodate all customers? And how can the rooms be allocated?

Example:

Input:  n = 3, arr = {{1, 2}, {2, 4}, {4, 4}}

Output:

2
1 2 1 

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

void roomAllocation(int n, vector<array<int, 3>> &a)
{

    sort(a.begin(), a.end());
    vector<int> ans(n);
    priority_queue<array<int, 2>,
                   vector<array<int, 2>>,
                   greater<array<int, 2>>>
        pq;
    for (int j = 0; j < n; j++)
    {
        int l = a[j][0];
        int r = a[j][1];
        int i = a[j][2];

        if (pq.empty() || l <= pq.top()[0])
        {
            ans[i] = pq.size() + 1;
        }
        else
        {
            ans[i] = pq.top()[1];
            pq.pop();
        }
        pq.push({r, ans[i]});
    }
    cout << pq.size() << "\n";
    for (int x : ans)
        cout << x << " ";
    cout << "\n";
}

int main()
{
    int n = 3;
    vector<vector<int>> arr = {{1, 2}, {2, 4}, {4, 4}};
    vector<array<int, 3>> a(n);
    for (int i = 0; i < n; i++)
    {
        int l = arr[i][0], r = arr[i][1];

        a[i] = {l, r, i};
    }
    roomAllocation(n, a);

    return 0;
}