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.
Press Submit to check your solution.
Back to lesson: Practice: Contest Problem Set