#1326. LIVE - Truyền hình trực tiếp

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

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ó N\ (1≤N≤10^5) hoạt động khác nhau diễn ra. Hoạt động thứ i sẽ được bắt đầu tại thời điểm S_i và kết thúc tại thời điểm E_i ( S_i, E_i nguyên và 1≤S_i < E_i ≤10^8 ).

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 x và hoạt động khác bắt đầu tại thời điểm x 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:          :              :     <==>     :              :

5 hoạt động diễn ra với các khoảng thời gian (2,4), (1,12), (4,5), (7,10) (7,8) . Kết quả là ta có thể chọn hoạt động 1, 3, 4 để truyền hình trực tiếp. Nếu ta chọn hoạt động 2 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 4, 5 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, 3 là con số lớn nhất (!!!)

Dữ liệu vào:

  • Dòng đầu chứa số nguyên N ;
  • N dòng tiếp theo, dòng thứ i chứa hai số nguyên S_i E_i .

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.

Ví dụ:

Dữ liệu vào:
5
2 4
1 12
4 5
7 10
7 8
Dữ liệu ra:
3