Có n cuộc họp, cuộc họp thứ i
bắt đầu vào thời điểm ai và kết thúc ở thời điểm bi. Do chỉ có một phòng hội
thảo nên 2 cuộc họp bất kì sẽ được cùng bố trí phục vụ nếu khoảng thời gian làm
việc của chúng chỉ giao nhau tại đầu mút. Hãy bố trí phòng họp để phục vụ được
nhiều cuộc họp nhất.
Hướng dẫn:
Sắp xếp các cuộc họp tăng dần
theo thời điểm kết thúc (bi). Thế thì cuộc họp i sẽ bố trí được sau cuộc họp j
nếu và chỉ nếu j<i và bj<=ai. Yêu cầu bố trí được nhiều cuộc họp nhất có
thể đưa về việc tìm dãy các cuộc họp dài nhất thoả mãn điều kiện trên
Không có nhận xét nào:
Đăng nhận xét