Cho một tập hợp hoạt động , trong đó mỗi hoạt động đều yêu cầu sử dụng cùng một tài nguyên (ví dụ như hội trường diễn thuyết), và tại cùng một thời điểm chỉ có một hoạt động được sử dụng tài nguyên này. Mỗi hoạt động có thời gian bắt đầu và thời gian kết thúc , với . Nếu hoạt động được chọn, nó sẽ chiếm dụng tài nguyên trong khoảng thời gian .
Nếu khoảng thời gian và không giao nhau, ta nói hoạt động và hoạt động là tương thích (compatible). Nghĩa là, khi hoặc , thì hoạt động và hoạt động tương thích. Hãy chọn ra một tập hợp lớn nhất gồm các hoạt động tương thích với nhau.
Dữ liệu:
Dòng đầu tiên chứa một số nguyên .
dòng tiếp theo, mỗi dòng chứa hai số nguyên và .
Kết quả:
Xuất ra số lượng hoạt động lớn nhất có thể chọn sao cho chúng tương thích với nhau.
