問題描述

有一間大型飯店，接下來會有 $n$ 位顧客入住

每位顧客都希望單獨入住一個房間

你知道每位顧客的入住日與退房日

若第一位顧客的退房日早於第二位顧客的入住日，則這兩位顧客可以使用同一個房間（輪流入住）

你的任務：

請問最少需要幾間房間，才能容納所有顧客？

每位顧客該分配到哪一間房間？

練習題

連結：https://cses.fi/problemset/task/1164/

使用 priority_queue 維護正在使用中的房間，依據「最早退房」的策略重複分配房間

可以先根據抵達時間排序

接著遍歷房客

如果目前沒有人住或房客抵達的時間比目前住宿中最早的離開時間還早，代表要再多一間房間

否則房客抵達的時候，原本住宿中最早離開的房客應該已經走了，可以直接入住那間空房

完整程式碼

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

struct Time {
    int arrival;
    int departure;
    int index;
};

bool cmp(Time a, Time b) {
    return a.arrival < b.arrival;
}

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> a;
    vector<Time> b;
    int ans[200005] = {0};
    for (int i = 0; i < n; i++) {
        int arrival, departure;
        cin >> arrival >> departure;
        a.push_back(make_pair(arrival, departure));
        Time k;
        k.arrival = arrival;
        k.departure = departure;
        k.index = i;
        b.push_back(k);
    }
    sort(b.begin(), b.end(), cmp);
    int roomCnt = 0;
    // pq 存 departure 跟 room number
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i = 0; i < n; i++) {
        if (pq.empty() || b[i].arrival <= pq.top().first) {
            roomCnt++;
            pq.push({b[i].departure, roomCnt});
            ans[b[i].index] = roomCnt;
        } else {
            int vacantRoom = pq.top().second;
            pq.pop();
            pq.push({b[i].departure, vacantRoom});
            ans[b[i].index] = vacantRoom;
        }
    }
    cout << roomCnt << '\n';
    for (int i = 0; i < n; i++) cout << ans[i] << " ";
}