Skip to main content

Practice · 4 of 4

Xem phim tối đa

CHALLENGE
Difficulty: intermediate+25 XP

**Bài toán.** n suất chiếu, suất i bắt đầu s[i] và kết thúc e[i] (s[i] < e[i]). Chọn số suất lớn nhất để xem sao cho không hai suất nào chồng nhau (suất bắt đầu đúng lúc suất trước kết thúc vẫn hợp lệ: s ≥ e_trước). In số suất tối đa. Luận điểm đổi chỗ: chọn suất KẾT THÚC SỚM NHẤT còn khả dĩ — bất kỳ nghiệm tối ưu nào đều đổi được sang lựa chọn này không xấu đi. Sort theo e, quét một lượt. Cái bẫy kinh điển: sort theo THỜI ĐIỂM BẮT ĐẦU — một suất dài sớm chiếm slot chặn mọi suất ngắn phía sau.

Back to lesson: Practice: Contest Problem Set