Quét sự kiện để tìm thời điểm cần nhiều phòng nhất

1. Chọn khoảng nửa mở

Buổi học được biểu diễn bằng [bắt đầu, kết thúc). Một phòng có thể dùng cho lớp kế tiếp ngay tại mốc kết thúc trong mô hình không có thời gian chuẩn bị. Tạo một sự kiện +1 ở đầu và −1 ở cuối. Nếu xử lý riêng từng sự kiện, tại một mốc phải xử lý các kết thúc trước các bắt đầu.

2. Suy ra bộ đếm đang hoạt động

Sau khi xử lý các sự kiện ở mốc t, bộ đếm bằng số khoảng chứa t. Giá trị lớn nhất qua các mốc là số buổi đồng thời cao nhất. Mô hình đồng nhất về phòng và bỏ qua hạn chế thiết bị có thể dùng con số đó để đánh giá nhu cầu phòng. Khi có phòng chuyên dụng, phải kiểm tra khả năng ghép lớp với phòng đủ điều kiện.

3. Đối chiếu ví dụ có điểm chạm

Ba buổi [8,10), [10,12), [9,11) đạt đỉnh hai. Buổi thứ nhất kết thúc đúng lúc buổi thứ hai bắt đầu. Nếu thêm bắt đầu trước khi giảm kết thúc tại mốc 10, thuật toán có thể báo ba buổi trong một thời điểm giả. Mã sắp xếp theo mốc và độ biến thiên, nên −1 đứng trước +1 ở cùng mốc.

Chạy ví dụ bằng python gt_quet_su_kien_phong.py.

def dinh_dong_thoi(cac_buoi):
    su_kien = []
    for dau, cuoi in cac_buoi:
        if dau >= cuoi:
            raise ValueError("Buổi học phải có thời lượng dương")
        su_kien.extend([(dau, 1), (cuoi, -1)])
    hien_tai = cao_nhat = 0
    for _, thay_doi in sorted(su_kien):
        hien_tai += thay_doi
        cao_nhat = max(cao_nhat, hien_tai)
    return cao_nhat

assert dinh_dong_thoi([(8, 10), (10, 12), (9, 11)]) == 2
assert dinh_dong_thoi([(8, 10), (10, 12)]) == 1
assert dinh_dong_thoi([]) == 0
print("Đỉnh đồng thời của ba buổi là 2.")

4. Mở rộng sang sử dụng phòng thực tế

Nếu cần 10 phút chuẩn bị phòng sau mỗi lớp, kéo dài mỗi khoảng sử dụng tài nguyên rồi tính lại. Với thời gian chuẩn bị phụ thuộc loại lớp kế tiếp, việc kéo dài đồng đều có thể đánh giá sai. Hãy lập bộ dữ liệu kiểm chứng gồm điểm chạm, lớp qua ngày và lịch phòng bị khóa.

Đọc thêm Tài liệu giải thuật của Princeton.