Du lịch (đề HSG 12 Khánh Hòa 2023)
Xem dạng PDFVườn hoa thành phố Đà Lạt là địa điểm du lịch thu hút nhiều du khách tới tham quan ngắm hoa và chụp ảnh. Tại đây có ~n~ loài hoa được đánh số từ ~1~ tới ~n~, loài hoa thứ ~i~ nở đẹp nhất trong khoảng thời gian từ ~a_i~ tới ~b_i~ (~a_i < b_i~) hàng năm.
Là một người yêu thích du lịch và đam mê chụp ảnh, Tí không bao giờ bỏ qua những địa điểm và khoảng thời gian đẹp nhất khi tham quan những địa điểm đó. Lần này, tuy thời gian có hơi gấp gáp, Tí chỉ có thể đến tham quan một lúc rồi đi ngay và chỉ kịp chụp một bức ảnh toàn cảnh vườn hoa. Nhưng may mắn là thời điểm chụp ảnh chính là thời điểm mà có nhiều loài hoa nở rộ nhất trong năm.
Yêu cầu: Đếm số lượng các loài hoa đang nở rộ trong bức ảnh Tí chụp.
Dữ liệu
- Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^5~).
- Dòng thứ ~i~ trong ~n~ dòng tiếp theo mỗi dòng ghi hai số nguyên dương ~a_i~ và ~b_i~ (~1 \le i \le n~; ~1 \le a_i < b_i \le 10^9~).
Kết quả
Một số nguyên dương duy nhất là đáp án của bài toán.
Ví dụ
DULICH.INP
6
1 2
2 3
2 5
5 7
6 7
9 11
DULICH.OUT
3
Giải thích: Thời điểm chụp hình có nhiều loài hoa nở rộ nhất là ~2~. Lúc này có ~3~ loài hoa đang nở rộ là loài hoa số ~1~, số ~2~ và số ~3~. (Khoảng thời gian nở là đoạn đóng, tính cả hai đầu mút ~a_i~ và ~b_i~.)
Giới hạn
- 40% số test tương ứng với 40% số điểm có ~1 \le n \le 10^3~; ~1 \le a_i < b_i \le 10^3~.
- 30% số test tương ứng với 30% số điểm có ~10^3 < n \le 10^5~; ~1 \le a_i < b_i \le 10^6~.
- 30% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm.
Bình luận