CSES 2. Room Allocation (1164)

출처: https://cses.fi/problemset/task/1164

---

문제 설명

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?

입력 양식

The first input line contains an integer n: the number of customers.

Then there are n lines, each of which describes one customer. Each line has two integers a and b: the arrival and departure day.

출력

Print first an integer kk: the minimum number of rooms required.

After that, print a line that contains the room number of each customer in the same order as in the input. The rooms are numbered 1,2,…,k 

입력 예

3
1 2
2 4
4 4

출력 예

2
1 2 1

제약조건

• 1 <= n <= 2x10^5
• 1 <= a <= b <= 10^9

---

문제 풀이 내용

도착일, 출발일과 몇번째 손님인지 저장해서, 도착일 순으로 정렬한다.

출발일과 몇개의 방이 사용중인지 priority queue 에 저장하고, 가장 빠른 출발일과 새로운 도착일을 비교해서 사용중인 방의 수를 변경한다.

프로그램 내용

...
    vector <tuple<int, int, int>> in_schedule;

    for (int idx = 0; idx < nCus; idx++)
        in_schedule.push_back(make_tuple(arr, dep, idx));

    priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > room_q;
    vector <int> nRoom(nCus);

    sort(in_schedule.begin(), in_schedule.end());

    for (auto it = in_schedule.begin(); it != in_schedule.end(); it++)
        int arr, dep, cust_id, current;
        tie(arr, dep, cust_id) = *it;

        if (room_q.empty() || get<0>(room_q.top()) >= arr)
            current = ++room_count;                 /// used room number increase
        else
            current = get<1>(room_q.top());         /// used room number remove
            room_q.pop();

        room_q.push(make_pair(dep, current));      /// depature day, customer
        nRoom[cust_id] = current;                  /// current used room
...

 

Sorting and Searching ( link )