Mô tả
Bến phà Cần Thờ ngày càng nhộn nhịp, ông Ba - tổ trưởng tổ điều hành - phải sắp xếp lịch cập rời cho từng chuyến tàu chở hàng hóa lên xuống miền Tây. Cầu cảng chính của bến chỉ có một chỗ đậu nên không bao giờ cho phép hai tàu neo đậu cùng lúc.
Mỗi chuyến tàu cập đúng s phút và rời đúng e phút. Nếu tàu A rời đúng lúc tàu B cập (nghĩa là thời gian kết thúc của tàu này bằng thời gian bắt đầu của tàu kia) thì coi như hai tàu không chồng lấn - tàu này vừa rời khỏi cầu là tàu kia neo vào ngay.
Ông Ba muốn đón càng nhiều chuyến tàu càng tốt trong ngày. Hãy giúp ông Ba tính xem tối đa có thể xếp bao nhiêu chuyến tàu vào một cầu mà không có bất kỳ hai chuyến nào chồng lấn thời gian.
Đầu vào
Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 1000) - số lượng chuyến tàu cần sắp xếp.
n dòng tiếp theo, mỗi dòng chứa hai số nguyên s và e (0 ≤ s < e ≤ 10^6) - thời điểm cập và thời điểm rời của chuyến tàu đó (đơn vị: phút tính từ đầu ngày).
Đầu ra
In ra một số nguyên duy nhất - số lượng chuyến tàu tối đa có thể đậu tại một cầu sao cho không có hai chuyến nào chồng lấn thời gian.
Ràng buộc
- 1 ≤ n ≤ 1000
- 0 ≤ s < e ≤ 10^6
- Thời gian tính bằng phút, không âm.
Ví dụ
Ví dụ 1:
Đầu vào: 4 1 3 2 4 3 5 0 6
Đầu ra: 2
Giải thích: Sắp xếp theo thời gian rời: [1,3] → [2,4] → [3,5] → [0,6]. Chọn tàu [1,3] trước (rời lúc 3). Tàu [2,4] cập lúc 2 - chồng lấn nên bỏ. Tàu [3,5] cập lúc 3 - đúng lúc tàu trước rời, không chồng lấn, chọn tiếp. Tàu [0,6] chồng lấn nên bỏ. Tổng cộng chọn được 2 chuyến tàu.
Ví dụ 2:
Đầu vào: 5 5 7 1 3 8 10 3 5 0 2
Đầu ra: 4
Giải thích: Sắp xếp theo thời gian rời: [0,2] → [1,3] → [3,5] → [5,7] → [8,10]. Chọn [0,2], rồi [3,5] (không chồng), rồi [5,7] (không chồng), rồi [8,10] (không chồng). Tàu [1,3] chồng với [0,2] nên bỏ. Tổng cộng 4 chuyến.
Ví dụ 3:
Đầu vào: 3 0 100 50 60 70 80
Đầu ra: 2
Giải thích: Chọn [50,60] và [70,80]. Tàu [0,100] quá dài, chồng lấn với mọi tàu khác, nên chỉ có thể chọn 1 trong nó hoặc chọn được 2 tàu ngắn.