Room Allocation (CSES 1164)
Đề bài
CSES 1164 – Room Allocation (Phân phòng)
Có một khách sạn lớn và sắp có $n$ khách hàng đến. Mỗi khách hàng muốn có một phòng đơn (một phòng chỉ dành riêng cho mình).
Bạn biết ngày đến và ngày đi của từng khách hàng. Hai khách hàng có thể ở cùng một phòng nếu ngày đi của khách thứ nhất sớm hơn ngày đến của khách thứ hai.
Hỏi cần ít nhất bao nhiêu phòng để phục vụ tất cả các khách hàng? Và phân phòng cho các khách như thế nào?
Dữ liệu vào:
- Dòng đầu tiên chứa số nguyên $n$: số lượng khách hàng.
- Tiếp theo là $n$ dòng, mỗi dòng mô tả một khách hàng gồm hai số nguyên $a$ và $b$: ngày đến và ngày đi.
Kết quả:
- Đầu tiên in ra một số nguyên $k$: số phòng ít nhất cần dùng.
- Sau đó in ra một dòng chứa số phòng của từng khách hàng, theo đúng thứ tự như trong dữ liệu vào. Các phòng được đánh số $1, 2, \ldots, k$. Bạn có thể in ra một phương án hợp lệ bất kỳ.
Ràng buộc:
- $1 \le n \le 2 \cdot 10^5$
- $1 \le a \le b \le 10^9$
Giới hạn: thời gian 1 giây, bộ nhớ 512 MB.
CSES 1164 – 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?
Input
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.
Output
Print first an integer $k$: 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, \ldots, k$. You can print any valid solution.
Constraints
- $1 \le n \le 2 \cdot 10^5$
- $1 \le a \le b \le 10^9$
Time limit: 1.00 s Memory limit: 512 MB
3
1 2
2 4
4 42
1 2 1Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Đề gốc là tiếng Anh nhưng ngắn gọn, ở trên mình đã dịch sang tiếng Việt. Mình giải thích lại cho bạn nào chưa hiểu: có một khách sạn lớn, xem như có vô số phòng luôn đi hen. Ta có danh sách $N$ khách đã đặt phòng trước, mỗi khách có 2 thông tin là ngày đến và ngày đi. Mỗi khách yêu cầu ở phòng đơn, tức là phòng đó chỉ có một mình khách đó ở. Hỏi khách sạn phải xếp phòng thế nào để đáp ứng đủ $N$ khách mà số phòng dùng là ít nhất, và in ra chi tiết khách nào ở phòng nào. Hai khách dùng chung được 1 phòng nếu ngày đi của khách thứ nhất nhỏ hơn hẳn ngày đến của khách thứ hai.
Với ví dụ của đề: chỉ cần 2 phòng. Khách 1 ở phòng 1, khách 2 ở phòng 2, khách 3 dùng lại phòng 1, vì lúc này phòng 1 đã trống: khách 1 rời phòng từ ngày 2, trong khi ngày 4 khách 3 mới tới ($2 \lt 4$).
2 1 2 cũng đúng. Nhưng 2 2 1 hay 1 1 2 thì sai: khách 2 không thể chung phòng với khách 1 (vì $2 \lt 2$ là sai), cũng không thể chung phòng với khách 3 (vì $4 \lt 4$ là sai).Khi nhìn vào bài có $N$ tối đa $2 \cdot 10^5$ thì nhẩm tính được ngay: muốn chạy trong 1 giây thì toàn bài phải có độ phức tạp $O(N \log N)$ trở xuống. Nếu $O(N^2)$ thì $N^2 = 4 \cdot 10^{10}$, quá giới hạn $10^8$ ⇒ chắc chắn TLE. Còn $N \log N \approx 18 \cdot 2 \cdot 10^5 = 3{,}6 \cdot 10^6$ thì yên tâm. Nhìn vào giới hạn độ lớn mà ước tính độ phức tạp cần có, từ đó định hình ra cách giải quyết, đó là thói quen tốt các bạn nên tập.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Sắp xếp theo ngày đến, tìm phòng trống tuần tự – O(N²)
Với bài này, cỡ nào trước tiên ta cũng phải sắp xếp danh sách $N$ khách tăng dần theo ngày đến để có trật tự mà xét duyệt, chứ danh sách đang lộn xộn thế này là không làm được.
Sau khi sắp xếp, khách thứ $i$ chỉ có khả năng dùng chung phòng với các khách trước đó ($i - 1$, $i - 2$, …), vì ngày đến của họ $\le$ ngày đến của khách $i$. Còn các khách $i + 1$, $i + 2$… có ngày đến $\ge$ khách $i$ nên lúc đang xét khách $i$ thì chưa tính tới họ (khi xét tới khách $i + 1$ thì chuyện "dùng chung với khách $i$" sẽ được tính sau).
x, ngày đi y, ta lưu thêm mã id của mỗi khách (từ $0$ đến $N - 1$). Khi tính được khách a[i] ở phòng r thì gán b[a[i].id] = r. Cuối cùng chỉ việc in mảng b từ $0$ đến $N - 1$.Cách xử lý: duyệt các khách theo thứ tự đã sắp xếp. Với mỗi khách, ta tìm xem có phòng nào đã trống chưa, tức là có khách trước đó có ngày đi < a[i].x không. Có thì khách $i$ lấy luôn phòng đó, không có thì mở phòng mới (cnt++).
last[r] = ngày đi của khách sau cùng đang giữ phòng r, rồi duyệt tuần tự các phòng $1..cnt$.Vấn đề là bước tìm tuần tự này. Trong tình huống mọi khách đều phải mở phòng mới (ví dụ đơn giản là tất cả cùng đến một ngày), khách thứ $i$ phải xét hết mọi phòng trước đó mà không tìm được phòng nào. Số lần xét là $1 + 2 + \ldots + (N - 1) = \dfrac{N(N - 1)}{2}$, với $N = 2 \cdot 10^5$ là $19{.}999{.}900{.}000$ lần, gấp 200 lần ngưỡng $10^8$ ⇒ chắc chắn TLE. Mình vẫn đưa cách này để các bạn thấy rõ vì sao phải cải tiến.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
struct Data{
int x, y, id;
};
bool cmp(const Data &a, const Data &b){
return a.x < b.x;
}
Data a[200000];
int last[200001];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; ++i){
cin >> a[i].x >> a[i].y;
a[i].id = i;
}
sort(a, a + n, cmp);
int b[n];
int cnt = 0;
for(int i = 0; i < n; ++i){
int room = 0;
for(int r = 1; r <= cnt; ++r){
if(last[r] < a[i].x){
room = r;
break;
}
}
if(room == 0){
room = ++cnt;
}
last[room] = a[i].y;
b[a[i].id] = room;
}
cout << cnt << endl;
for(int i = 0; i < n; ++i){
cout << b[i] << " ";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = sorted((int(data[2 * i + 1]), int(data[2 * i + 2]), i) for i in range(n))
b = [0] * n
last = [0] # last[r] = ngày đi của khách cuối cùng đang giữ phòng r (phòng đánh số từ 1)
cnt = 0
for x, y, idx in a:
room = 0
for r in range(1, cnt + 1):
if last[r] < x:
room = r
break
if room == 0:
cnt += 1
room = cnt
last.append(0)
last[room] = y
b[idx] = room
print(cnt)
print(*b)
main()Đánh giá độ phức tạp của cách làm này:
- Không gian: mảng
a,b,last⇒ $O(N)$. - Thời gian: $O(N \log N)$ sắp xếp + mỗi khách duyệt tối đa $cnt$ phòng ⇒ $O(N \cdot K)$ với $K$ là số phòng, tệ nhất $K = N$ ⇒ $O(N^2)$.
Cách 2Duy trì danh sách ngày đi có thứ tự bằng multiset – O(N·logN)
Để không phải xét tuần tự thì ta phải thấy được mấu chốt vì sao cách 1 phải đi tìm tuần tự: các khách trước đó tuy được sắp tăng dần theo ngày đến, nhưng ngày đi thì đang lộn xộn (ta chỉ sắp theo ngày đến, ngày đi bị kéo theo). Chính vì lộn xộn nên muốn biết có ai có ngày đi $\lt$ a[i].x hay không thì chỉ còn cách dò từng người.
Đến đây chắc các bạn cũng lờ mờ nhận ra rồi chứ? Ta cần có danh sách ngày đi của các phòng đang dùng, luôn được sắp tăng dần (gọi là danh sách $B$). Khi đó chỉ cần lấy phần tử đầu tiên $B_0$ (nhỏ nhất) ra so:
- Nếu $B_0 \lt$
a[i].x⇒ phòng của người có ngày đi $B_0$ đã trống, khách $i$ vào ở luôn, khỏi mở phòng mới. Cập nhật $B_0$ thànha[i].y. - Nếu $B_0 \ge$
a[i].x⇒ chắc chắn không còn phòng nào trống, vì $B$ đang tăng dần: phần tử nhỏ nhất còn không nhỏ hơn thì làm gì còn phần tử nào nhỏ hơn được nữa. Mở phòng mới và thêma[i].yvào $B$.
Cái khó là sau mỗi lần cập nhật/thêm, $B$ phải giữ được thứ tự tăng dần để còn xét tiếp khách $i + 1$. Nếu dùng mảng 1 chiều thì mỗi lần như vậy lại phải sắp xếp lại mảng, chi phí rất lớn và có thể TLE.
priority_queue) hay multiset. Bài này mình dùng multiset rất tiện. Muốn hiểu bản chất vì sao nó làm được như vậy thì hơi phức tạp, nhưng gọi thư viện ra xài thì rất đơn giản, các bạn cứ áp dụng quen là sẽ rành thôi.Chi tiết cài đặt:
multisetlưupair:firstlà ngày đi,secondlà mã phòng của khách có ngày đi đó. Vớipairthìmultisetmặc định sắp theofirsttrước (tương tựset,map, sortvector…), nênmts.begin()luôn là phòng có ngày đi sớm nhất.multisetkhông cho sửa trực tiếp một phần tử. Nên khi cần "cập nhật $B_0$ =a[i].y" thì ta xóamts.begin()đi rồi thêm{a[i].y, mã phòng cũ}vào.- Ngược lại thì thêm
{a[i].y, ++cnt}(phòng mới). Và dù trường hợp nào cũng nhớ ghi mã phòng vàob[a[i].id]vì sau cùng ta xuất mảngb.
Em nhập danh sách khách (mỗi khách 2 số: đến, đi) rồi bấm Tiếp để xem từng khách được xếp phòng thế nào và multiset thay đổi ra sao:
Mỗi hàng P1, P2… là một phòng, mỗi thanh màu là một khách ở trong các ngày từ ngày đến tới ngày đi (tính cả 2 đầu). Các bạn để ý: hai thanh trong cùng một hàng không bao giờ chạm nhau, đúng điều kiện "ngày đi của khách trước nhỏ hơn hẳn ngày đến của khách sau".
Source code để các bạn tham khảo thấy rõ với tất cả những gì mình đã phân tích ở trên:
#include <bits/stdc++.h>
using namespace std;
struct Data{
int x, y, id;
};
bool cmp(const Data &a, const Data &b){
return a.x < b.x;
}
Data a[200000];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; ++i){
cin >> a[i].x >> a[i].y;
a[i].id = i;
}
sort(a, a + n, cmp);
int b[n];
multiset<pair<int, int>> mts;
int cnt = 0;
mts.insert({a[0].y, ++cnt});
b[a[0].id] = cnt;
for(int i = 1; i < n; ++i){
auto it = mts.begin();
if(it->first < a[i].x){
b[a[i].id] = it->second;
mts.erase(it);
mts.insert({a[i].y, b[a[i].id]});
}
else{
mts.insert({a[i].y, ++cnt});
b[a[i].id] = cnt;
}
}
cout << cnt << endl;
for(int i = 0; i < n; ++i){
cout << b[i] << " ";
}
return 0;
}import sys
from heapq import heappush, heapreplace
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
x = list(map(int, data[1:2 * n + 1:2])) # ngày đến
y = list(map(int, data[2:2 * n + 2:2])) # ngày đi
# sắp các chỉ số khách tăng dần theo ngày đến (thay cho mảng struct + cmp)
order = sorted(range(n), key=x.__getitem__)
b = [0] * n
# heap đóng vai trò multiset: mỗi phần tử "gói" cặp (ngày đi, mã phòng)
# thành 1 số nguyên ngày_đi * 2^18 + mã_phòng (mã phòng <= 2*10^5 < 2^18)
heap = []
cnt = 0
for i in order:
if heap and (heap[0] >> 18) < x[i]:
room = heap[0] & 262143
heapreplace(heap, (y[i] << 18) | room) # xóa phần tử nhỏ nhất rồi thêm phần tử mới
else:
cnt += 1
room = cnt
heappush(heap, (y[i] << 18) | room)
b[i] = room
sys.stdout.write(str(cnt) + "\n" + " ".join(map(str, b)) + "\n")
main()Giải thích một số chỗ trong code ở trên:
- 3 dòng đầu hàm main (
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);) giúp đẩy nhanh tốc độ nhập xuất với C++. Bài này input có thể lên đến $4 \cdot 10^5$ số, output $2 \cdot 10^5$ số, là số lượng lớn, nên thêm 3 dòng này vào cho chương trình chạy nhanh hơn (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là ra rất nhiều bài giải thích nhé). - Mảng
Data a[200000]khai báo toàn cục bên trên hàm main: $N$ tối đa $2 \cdot 10^5$ và mỗi phần tử có 3 thành phần. Theo kinh nghiệm của mình, mảng tĩnh lớn cỡ vượt $3 \cdot 10^5$ phần tử thì không nên khai báo trong hàm vì bộ nhớ stack có thể không chứa nổi. Lúc này hoặc đem mảng ra ngoài làm biến toàn cục (không dùng vùng nhớ stack nên chứa được lớn hơn), hoặc cấp phát độngData *a = new Data[n];, hoặc dùng luônvector. - Hàm
cmp:return a.x < b.x;là viết gọn củaif(a.x < b.x) return true; return false;, nghĩa là $x$ của A nhỏ hơn $x$ của B thì làtrue, tức chúng đã đứng đúng chỗ ⇒ danh sách tăng dần theo $x$. Nếu sai thìsortsẽ đổi chỗ 2 tụi nó để về lại đúng, các bạn có thể hiểu theo ý như vậy cho dễ nhớ. sort(a, a + n, cmp);sắp xếp mảngatừ đầu mảng, đủ $n$ phần tử, theo hàmcmp(tăng dần theo ngày đến). Phải dùng thuật sắp xếp $O(N \log N)$, chứ tự cài sắp xếp $O(N^2)$ là TLE như mình phân tích ở đầu.- Khách đầu tiên
a[0]chắc chắn ở phòng 1 nên mình thêm{a[0].y, ++cnt}vào multiset và gánb[a[0].id] = cnttrước, rồi vòng lặp chạy từi = 1. - Bản Python: Python không có
multiset, nhưng ở đây ta chỉ cần lấy/xóa phần tử nhỏ nhất nên dùng hàng đợi ưu tiênheapqlà đủ (heap[0]là phần tử nhỏ nhất,heapreplace= xóa nhỏ nhất rồi thêm mới). Để chạy nhanh, mình "gói" cặp (ngày đi, mã phòng) thành 1 số nguyênngày_đi * 2^18 + mã_phòng(mã phòng $\le 2 \cdot 10^5 \lt 2^{18}$), so sánh số này cũng chính là so theo ngày đi trước.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(3N)$ cho mảng
a+ $O(N)$ mảngb+ $O(N)$ cho multiset. Theo quy tắc cộng BigO thì lấy thành phần lớn nhất ⇒ $O(N)$. - Thời gian: $O(N)$ đọc dữ liệu + $O(N \log N)$ sắp xếp + $O(N \log N)$ toàn bộ thao tác thêm/xóa trên multiset + $O(N)$ in mảng
b⇒ tổng quát $O(N \log N)$, yên tâm không bị TLE như đã phân tích ở đầu bài.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét