題意#
題目給定飯店將有 \( n \) 位客人入住。
我們已知每位客人的「入住日期」與「退房日期」。
若前一位客人的退房日期「嚴格早於」下一位客人的入住日期，兩人便可安排在同一間客房。
我們需要求出滿足所有客人所需的最少客房數，並具體列出每位客人分配到的房號。
思路#
本題為經典的貪婪法與排程問題。
首先將所有客人的「入住時間」從小到大排序，依序處理住房需求。
處理過程中，需掌握兩項資訊：「使用中客房的退房時間」及「目前的可用空房」。
我們可以使用兩個遞增排序的 Priority Queue（Min-Heap）來維護：
pq：記錄已被入住的客房狀態，以「退房時間」為排序基準，以快速找出最早空出的房間。room：儲存「目前空閒」的房間號碼。
當處理新客人時：
先檢查 pq，將所有退房時間早於該客人入住時間的房間移出 pq，並將房號加入 room。
釋放所有可用空房後，若 room 不為空，則分配一間空房給該客人；若 room 內無房，表示現有客房已滿，必須新開一間獨立客房。
安排完畢後，將客人的退房時間與配發的房號推入 pq 中。
遍歷所有客人後，即可算出最少房間總數與對應名單。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n; cin >> n;
// 儲存每個人的 {入住時間, 退房時間, 原本的輸入順序 ID}
vector<tuple<int, int, int>> v(n);
int id = 0;
for (auto &[a, b, i] : v) cin >> a >> b, i = id++;
// 按照入住時間從小到大排序
sort(all(v));
// pq：紀錄 {退房時間, 房號}，以退房時間早的優先
priority_queue<PII, vector<PII>, greater<>> pq;
// room：存放目前可用的空房間號碼，房號小的優先
priority_queue<int, vector<int>, greater<>> room;
id = 0;
vector<int> ans(n);
for (auto &[sta, ed, i] : v) {
// 先結算：把所有「退房時間 < 新客人入住時間」的客房清空，釋放至空房清單
while (pq.size() && pq.top().fi < sta) {
room.push(pq.top().se);
pq.pop();
}
// 分配房間：若沒有空房可用，則只能新開一間獨立的房間 (號碼累加)
if (room.empty()) room.push(++id);
// 將房間安排給這位客人（利用原本的輸入順序 i 來存答案）
ans[i] = room.top();
// 將這位客人的退房時間與房號推入 pq 佔用
pq.push({ed, room.top()}); room.pop();
}
// 最大開出的房號 id 即為最小房數
cout << id << '\n';
for (auto &i : ans) cout << i << ' ';
}
