Xếp lịch thi không trùng giờ bằng Python
Bài 9/10 · Chương 25
Bài tập phỏng vấn Python
- 8 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 11
Bài toán xếp lịch thi trong Python hỏi: một phòng thi có nhiều môn xin giờ, chọn được nhiều môn nhất là bao nhiêu mà không hai môn nào trùng giờ. Trang này giải bằng cách tham lam (greedy): sắp các môn theo giờ kết thúc rồi chọn lần lượt, giải thích vì sao cách đó đúng, rồi cho bạn một bài tập được chấm ngay trên trang.
Cần biết trước: sắp xếp list, hàm lambda và tuple.
Đề bài
Phòng thi số 3 chỉ có một bộ máy chiếu, nên mỗi lúc chỉ thi được một môn. Bảy môn xin giờ, mỗi môn là một tuple (tên, giờ bắt đầu, giờ kết thúc), giờ tính tròn trong ngày. sorted() với key=lambda mon: mon[2] xếp các môn theo phần tử thứ ba, giờ kết thúc:
cac_mon = [("Toán", 7, 9), ("Văn", 8, 10), ("Anh", 9, 11),
("Lý", 10, 12), ("Hóa", 11, 12), ("Sử", 7, 12),
("Sinh", 12, 14)]
theo_gio_ket_thuc = sorted(cac_mon, key=lambda mon: mon[2])
for ten, bat_dau, ket_thuc in theo_gio_ket_thuc:
print(f"{ten:<5}{bat_dau:>3}h -{ket_thuc:>3}h")KẾT QUẢ
Toán 7h - 9h
Văn 8h - 10h
Anh 9h - 11h
Lý 10h - 12h
Hóa 11h - 12h
Sử 7h - 12h
Sinh 12h - 14hHai môn trùng giờ khi khoảng thời gian của chúng chồng lên nhau. Môn kết thúc lúc 9 giờ và môn bắt đầu lúc 9 giờ thì không trùng: thí sinh môn trước vừa ra, thí sinh môn sau vào. Viết hàm cho biết phòng nhận được nhiều nhất bao nhiêu môn. Trước khi viết code, hỏi lại: hai môn chạm giờ có được không, và cần số môn hay cần cả tên các môn.
Cách tham lam: chọn môn kết thúc sớm nhất
Cách tham lam quyết định từng bước theo lựa chọn tốt nhất ngay lúc đó và không quay lại sửa. Ở bài này, lựa chọn tốt nhất là môn kết thúc sớm nhất trong số các môn còn xếp được, vì nó trả phòng sớm nhất cho các môn sau. het_gio nhớ giờ phòng trống lại:
def dem_toi_da(ds):
so_mon = 0
het_gio = 0
for ten, bat_dau, ket_thuc in sorted(ds, key=lambda m: m[2]):
if bat_dau >= het_gio:
print("Chọn", ten, "đến", ket_thuc, "giờ")
so_mon += 1
het_gio = ket_thuc
return so_mon
cac_mon = [("Toán", 7, 9), ("Văn", 8, 10), ("Anh", 9, 11),
("Lý", 10, 12), ("Hóa", 11, 12), ("Sử", 7, 12),
("Sinh", 12, 14)]
print(dem_toi_da(cac_mon), "môn")KẾT QUẢ
Chọn Toán đến 9 giờ
Chọn Anh đến 11 giờ
Chọn Hóa đến 12 giờ
Chọn Sinh đến 14 giờ
4 mônVăn bị bỏ vì bắt đầu lúc 8 giờ, khi Toán còn thi. Lý và Hóa cùng kết thúc lúc 12 giờ, nhưng Lý bắt đầu lúc 10 giờ, phòng còn bận Anh, nên tới lượt Hóa mới được chọn. sorted() trả về một list mới, nên cac_mon của nơi gọi hàm giữ nguyên thứ tự. Đổi ("Sinh", 12, 14) thành ("Sinh", 13, 14) rồi chạy lại: hàm vẫn chọn Sinh, dòng cuối vẫn là 4 môn.
Vì sao không chọn môn bắt đầu sớm nhất
Chọn môn bắt đầu sớm nhất nghe tự nhiên, vì phòng không bỏ trống lúc đầu buổi. Nhưng một môn dài bắt đầu sớm sẽ giữ phòng suốt buổi.
Chọn môn ngắn nhất cũng sai. Với ba môn (7, 10), (10, 13) và (9, 11), môn ngắn nhất là (9, 11), dài hai tiếng, nhưng nó chồng lên cả hai môn kia: chọn nó thì lịch chỉ có 1 môn, trong khi hai môn dài ba tiếng đặt liền nhau được.
Vì sao chọn môn kết thúc sớm nhất là đúng
Giả sử có một lịch tốt nhất nào đó, và môn đầu tiên của nó không phải môn kết thúc sớm nhất A. Đổi môn đầu tiên đó lấy A: A kết thúc không muộn hơn, nên mọi môn sau của lịch vẫn không trùng, và số môn giữ nguyên. Vậy luôn có một lịch tốt nhất bắt đầu bằng A.
Sau khi chọn A, phần còn lại là cùng bài toán đó trên các môn bắt đầu từ giờ A kết thúc trở đi. Lặp lại lý lẽ trên cho từng bước, bạn được đúng lịch mà vòng lặp chọn ra. Người ta gọi kiểu lý lẽ này là đổi chỗ (exchange argument): đổi một lựa chọn của lời giải tốt nhất lấy lựa chọn tham lam mà không làm nó kém đi.
Số bước: sắp xếp tốn O(n log n), vòng lặp đi qua list một lượt, nên cả hàm là O(n log n) với n môn.
Nói gì với người phỏng vấn
Hỏi lại đề trước: hai môn chạm giờ có được không, cần số môn hay danh sách môn. Viết xong, bạn trình bày:
"Đây là bài interval scheduling. Tôi sắp các môn theo giờ kết thúc rồi đi một lượt, chọn môn nào bắt đầu từ lúc phòng trống trở đi."
"Cách này đúng vì luôn đổi được môn đầu của một lịch tốt nhất lấy môn kết thúc sớm nhất mà không mất môn nào."
"Chọn theo giờ bắt đầu hay theo môn ngắn nhất đều có phản ví dụ, nên tôi không dùng."
"Sắp xếp là O(n log n), vòng chọn là O(n). Tôi đã xét list rỗng, hai môn chạm giờ và hai môn cùng giờ kết thúc."
Kiểm tra nhanh
Hàm
dem_toi_dacủa mục "Cách tham lam: chọn môn kết thúc sớm nhất" trả về số nào với list[("Toán", 7, 9), ("Văn", 8, 10), ("Anh", 9, 11)]?Với
het_gio = 9, môn("Anh", 9, 11)có được chọn không nếu điều kiện viếtbat_dau > het_gio?- Có, vì Anh bắt đầu đúng lúc phòng trống
- Không, vì
9 > 9sai - Python báo lỗi vì so hai số bằng nhau
Những câu nào đúng về cách tham lam của trang?
- Chọn môn kết thúc sớm nhất trả phòng sớm nhất cho các môn sau
- Chọn môn bắt đầu sớm nhất luôn cho số môn bằng cách chọn môn kết thúc sớm nhất
- Chọn môn ngắn nhất trước là cách đúng, vì môn ngắn chiếm ít giờ
- Hàm tốn O(n log n) vì phải sắp xếp trước khi chọn
Bài tập
Xếp lịch thi có giờ dọn phòng
Sau mỗi môn, phòng cần nghi giờ dọn dẹp: môn sau chỉ bắt đầu được từ giờ kết thúc của môn trước cộng nghi. Viết hàm xep_lich(ds, nghi) chọn nhiều môn nhất bằng cách tham lam của trang: duyệt ds theo giờ kết thúc bằng sorted(), cùng giờ kết thúc thì giữ thứ tự trong ds.
Trả về: tên các môn đã chọn theo thứ tự thi, một list.
dslà list tuple(tên, giờ bắt đầu, giờ kết thúc), giờ là số nguyên không âm.Hàm không được sửa list
ds.xep_lich(CAC_MON, 0)là["Toán", "Anh", "Hóa", "Sinh"].
Ôn lại: hàm lambda.
CAC_MON = [("Toán", 7, 9), ("Văn", 8, 10), ("Anh", 9, 11),
("Lý", 10, 12), ("Hóa", 11, 12), ("Sử", 7, 12),
("Sinh", 12, 14)]
def xep_lich(ds, nghi):
pass # Viết thân hàm thay cho dòng nàyCâu hỏi thường gặp
Interval scheduling trong Python có cần thư viện riêng không?
Không. Bài chọn nhiều khoảng không chồng nhau nhất chỉ cần sorted() với một khóa và một vòng lặp, như mục cách tham lam. Khi bài toán có thêm ràng buộc như ưu tiên môn (có trọng số) hay sức chứa thì cách tham lam không còn đúng: cần quy hoạch động hoặc một thư viện tối ưu.
Bài toán xếp lịch nhiều phòng thì giải thế nào?
Câu hỏi đổi thành "cần ít nhất bao nhiêu phòng để thi hết mọi môn". Lời giải quen thuộc sắp các môn theo giờ bắt đầu và theo dõi các phòng đang bận, mở phòng mới khi không phòng nào trống. Vẫn là tham lam, nhưng khóa sắp xếp khác với trang này, nên đừng chép nguyên vòng lặp ở đây.
Thuật toán tham lam có luôn cho lời giải tốt nhất không?
Không. Tham lam chỉ đúng khi chứng minh được như mục "Vì sao chọn môn kết thúc sớm nhất là đúng"; chọn môn ngắn nhất là một kiểu tham lam sai. Trước khi dùng, hãy thử tìm một phản ví dụ nhỏ, và xem lại cách sắp xếp list với khóa phù hợp.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.