Bố trí phòng họp
Đề bài
Có $n$ cuộc họp đánh số từ 1 đến $n$ đăng ký làm việc tại một phòng hội thảo. Cuộc họp $i$ cần được bắt đầu ngay sau thời điểm $s_i$ và kết thúc tại thời điểm $f_i$. Hỏi có thể bố trí phòng hội thảo phục vụ được nhiều nhất bao nhiêu cuộc họp, sao cho khoảng thời gian làm việc của hai cuộc họp bất kỳ là không giao nhau.
Input:
- Dòng đầu tiên chứa số nguyên dương $n$ $(n \le 10^6)$.
- Dòng thứ $i$ trong số $n$ dòng tiếp theo chứa hai số nguyên dương $s_i, f_i$ $(s_i < f_i \le 10^9)$ $(1 \le i \le n)$.
Output: dòng đầu tiên ghi số $K$ là số các cuộc họp được chấp nhận phục vụ.
Subtask:
- 10% số test đầu tiên có $n \le 10$;
- 10% số test tiếp theo có $n \le 20$;
- 10% số test tiếp theo có $n \le 10^3$;
- 30% số test tiếp theo có $n \le 10^4$;
- 30% số test tiếp theo có $n \le 10^5$;
- 10% số test còn lại có $n \le 10^6$.
5
7 9
2 4
1 3
1 6
3 73Giải thích ví dụ: chọn cuộc họp 3 $(1, 3]$, cuộc họp 5 $(3, 7]$ và cuộc họp 1 $(7, 9]$. Cuộc họp 5 bắt đầu ngay sau thời điểm 3 – đúng lúc cuộc họp 3 kết thúc – nên hai cuộc họp này không giao nhau. Vậy mỗi cuộc họp là nửa khoảng $(s_i, f_i]$ và điều kiện để xếp cuộc họp $j$ sau cuộc họp $i$ là $s_j \ge f_i$ (được phép bằng).
Lời mở đầu
Đây là bài toán chọn hoạt động (activity selection) kinh điển – ví dụ mở đầu của gần như mọi giáo trình về thuật toán tham lam. Bài viết đi từ vét cạn mọi tập con, qua quy hoạch động $O(n^2)$, tới thuật toán tham lam $O(n \log n)$ ngắn gọn bất ngờ, kèm lý do vì sao tham lam ở đây lại đúng.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
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:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test, khớp chính xác với 6 subtask đề ghi:
| Test | n | Thời điểm | Số cuộc họp trùng nhau (max) | Đáp án |
|---|---|---|---|---|
| 1 – 10 | 2 … 10 | 1 … 30 | 1 | 1 … 4 |
| 11 – 20 | 11 … 20 | 1 … 30 | 2 | 3 … 8 |
| 21 – 30 | 1 000 … 1 000 | 1 … 999 985 825 | 2 | 44 … 53 |
| 31 – 60 | 10 000 … 10 000 | 1 … 999 999 700 | 56 | 144 … 170 |
| 61 – 90 | 100 000 … 100 000 | 1 … 999 999 855 | 1 485 | 459 … 503 |
| 91 – 100 | 1 000 000 … 1 000 000 | 1 … 999 999 829 | 31 689 | 1 455 … 1 532 |
- Test 1 – 20: thời điểm chỉ từ 1 tới 30, nhiều cuộc họp chạm đầu nhau ($s_j = f_i$) – đây là chỗ bắt lỗi ai dùng
>thay cho>=. - Test 21 – 100: thời điểm tới gần $10^9$; mỗi mức đều dùng $n$ đúng bằng giới hạn trên của subtask. Test lớn có khá nhiều cuộc họp lặp lại y hệt nhau (cột thứ 4: số cuộc họp trùng với một cuộc khác), điều này không ảnh hưởng thuật toán.
- Mọi test đều thoả $s_i < f_i$.
Bảng subtask và cách nào ăn được:
| Subtask | Điều kiện | Test | Cách 1 | Cách 2 | Cách 3 |
|---|---|---|---|---|---|
| 1 (10%) | $n \le 10$ | 1 – 10 | ✔ | ✔ | ✔ |
| 2 (10%) | $n \le 20$ | 11 – 20 | ✔ | ✔ | ✔ |
| 3 (10%) | $n \le 10^3$ | 21 – 30 | ✘ | ✔ | ✔ |
| 4 (30%) | $n \le 10^4$ | 31 – 60 | ✘ | ✔ | ✔ |
| 5 (30%) | $n \le 10^5$ | 61 – 90 | ✘ | ✘ | ✔ |
| 6 (10%) | $n \le 10^6$ | 91 – 100 | ✘ | ✘ | ✔ |
Cách 1Vét cạn mọi tập con – ăn 2 subtask đầu
Với $n \le 20$, ta thử hết $2^n$ tập con cuộc họp bằng bitmask: bit thứ $i$ của mask bằng 1 nghĩa là chọn cuộc họp $i$. Để kiểm tra một tập có hợp lệ không, mình sắp xếp các cuộc họp theo thời điểm kết thúc từ trước; khi đó các cuộc họp được chọn, xét theo thứ tự này, phải nối đuôi nhau: cuộc sau bắt đầu không sớm hơn lúc cuộc trước kết thúc ($s \ge$ last).
bool ok = true;, bước "last = ..." gộp luôn cnt++.- Lưu cặp
(f, s)(kết thúc đứng trước) đểsortmặc định sắp theo thời điểm kết thúc. - Vì các thời điểm đều dương nên khởi tạo
last = 0là "chưa có cuộc họp nào".
Kết quả chạy thật: bản C++ đúng 20/100 test – trọn subtask 1 và 2 (test 1 – 20), chậm nhất 0.01 giây. Từ test 21 ($n = 1000$) thì $2^n$ là con số khổng lồ, và 1 << n với int còn bị tràn số (hành vi không xác định – trên máy chấm vòng lặp không chạy lần nào và in ra 0) → sai. Bản Python đúng 19/20 test nhỏ (test 16 với $n = 20$ mất 1.15 giây), các test lớn quá thời gian.
Cách 2Quy hoạch động O(n²)
Vẫn sắp xếp theo thời điểm kết thúc. Gọi dp[i] là số cuộc họp nhiều nhất chọn được trong các cuộc họp $0..i$, với cuộc họp cuối cùng là $i$. Cuộc họp đứng ngay trước $i$ phải là một $j < i$ có $f_j \le s_i$, nên:
Đáp án là giá trị lớn nhất của dp.
Kết quả chạy thật: bản C++ đúng 60/100 test – trọn subtask 1 – 4 (test 1 – 60, $n \le 10^4$), chậm nhất 0.07 giây. Các test $n = 10^5$ trở lên cần cỡ $5 \cdot 10^9$ phép so sánh nên quá thời gian. Bản Python chỉ đúng 30/100 (tới $n = 1000$), với $n = 10^4$ đã mất hơn 2 giây.
Ý tưởngTham lam: luôn chọn cuộc họp kết thúc sớm nhất
Hãy nghĩ như người quản lý phòng: cuộc họp đầu tiên nên chọn là cuộc nào? Một cuộc họp kết thúc càng sớm thì phòng càng sớm trống, để lại nhiều thời gian nhất cho các cuộc họp sau. Từ đó ra thuật toán:
last = thời điểm kết thúc của cuộc họp vừa chọn. Cuộc họp nào có $s \ge$ last thì chọn ngay và gán last = f; ngược lại bỏ qua.Vì sao đúng? Gọi $x$ là cuộc họp kết thúc sớm nhất. Lấy một lời giải tối ưu bất kỳ, cuộc họp đầu tiên của nó là $y$ với $f_y \ge f_x$. Thay $y$ bằng $x$: mọi cuộc họp sau $y$ bắt đầu từ $f_y \ge f_x$ trở đi nên vẫn không giao với $x$ – số cuộc họp không đổi. Vậy luôn có lời giải tối ưu chứa $x$; bỏ $x$ và các cuộc họp giao với nó đi, lập luận y hệt cho phần còn lại.
Các cách "tham lam" khác trông cũng hợp lý nhưng sai:
- Chọn cuộc bắt đầu sớm nhất: với $(1, 100]$, $(2, 3]$, $(3, 4]$ sẽ chọn $(1, 100]$ và chỉ được 1, trong khi đáp án là 2.
- Chọn cuộc ngắn nhất: với $(1, 5]$, $(4, 6]$, $(6, 10]$ sẽ chọn $(4, 6]$ trước, chặn mất cả 2 cuộc còn lại → được 1, đáp án là 2.
Em nhập các cuộc họp (mỗi cuộc là cặp s f, các cuộc cách nhau dấu phẩy) rồi bấm Tiếp để xem thuật toán chọn từng cuộc:
Cách 3Tham lam O(n log n) – đủ điểm
- Điều kiện là
>=chứ không phải>: cuộc họp bắt đầu ngay sau lúc cuộc trước kết thúc là hợp lệ (như ví dụ của đề). - Phần tốn thời gian nhất là
sort; vòng chọn chỉ $O(n)$. Với $n = 10^6$ nhớ đọc nhanh bằngios::sync_with_stdio(0).
Kết quả chạy thật: bản C++ đúng 100/100 test, test chậm nhất (test 93, $n = 10^6$) chạy 0.35 giây – phần lớn thời gian là đọc dữ liệu và sắp xếp. Bản Python đúng 90/100, 10 test $n = 10^6$ bị quá 1 giây vì riêng việc đọc và sắp xếp $10^6$ cặp số trong Python đã quá chậm.
s >= last vì cuộc họp bắt đầu ngay sau thời điểm $s$.
Nhận xét
Đăng nhận xét