Nguồn: Bài tập thầy Nguyễn Thanh Bình Ôn ĐT Hải Phòng T10/2020
Nhân dịp kỷ niệm ngày thành lập, trường NT tổ chức nhiều hoạt động khác nhau (thể thao, văn nghệ, tọa đàm....). Trong số các học sinh của trường có nhiều người làm việc trong lĩnh vực phát thanh truyền hình. Những học sinh này đã quyết định tài trợ cho lễ kỷ niệm của nhà trường bằng cách thuê riêng một kênh truyền hình của VTV để truyền hình trực tiếp các hoạt động của nhà trường.
Theo kế hoạch đã được duyệt, sẽ có hoạt động khác nhau diễn ra. Hoạt động thứ sẽ được bắt đầu tại thời điểm và kết thúc tại thời điểm ( nguyên và ).
Do chỉ thuê được một kênh truyền hình nên vấn đề là làm thế nào có thể truyền hình trực tiếp được càng nhiều hoạt động càng tốt (các học sinh là những con người thành đạt nên tiền – thời gian truyền hình trực tiếp - không phải là vấn đề!!!). Tại một thời điểm chỉ có thể truyền hình trực tiếp được một hoạt động. Tuy nhiên nếu một hoạt động kết thúc ở thời điểm và hoạt động khác bắt đầu tại thời điểm thì cả hai hoạt động này đều có thể cùng được chọn để truyền hình trực tiếp. Bạn là học sinh chuyên tin, hãy giúp các anh chị giải quyết vấn đề trên.
Xét ví dụ dưới đây:
... 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
... |----|----|----|----|----|----|----|----|----|----|----|----|----
HD 1: <===:===> : : :
HD 2: <========:==============:==============:=============>:
HD 3: : <====> : : :
HD 4: : : <========:===> :
HD 5: : : <==> : :
Có hoạt động diễn ra với các khoảng thời gian và . Kết quả là ta có thể chọn hoạt động để truyền hình trực tiếp. Nếu ta chọn hoạt động thì không có hoạt động nào được truyền hình trực tiếp nữa, ngoài ra hai hoạt động không thể truyền hình trực tiếp cùng nhau. Do vậy có thể thấy trong ví dụ trên, là con số lớn nhất (!!!)
Dữ liệu vào:
Dòng đầu chứa số nguyên ;
dòng tiếp theo, dòng thứ chứa hai số nguyên và .
Dữ liệu ra:
Một số nguyên duy nhất là số hoạt động có thể truyền hình trực tiếp.
