Lịch quan sát không chồng lấn

Bối cảnh và bài toán

Một trạm quan sát có n phiên đo, mỗi phiên chiếm khoảng thời gian [a,b). Một thiết bị chỉ thực hiện được một phiên tại một thời điểm, nhưng có thể bắt đầu phiên mới đúng lúc phiên trước kết thúc. Cần thực hiện được nhiều phiên nhất.

Yêu cầu

Tìm số phiên tối đa có thể chọn mà không chồng lấn.

Input

• Dòng 1: n.
• n dòng tiếp: a b.

Output

In số phiên tối đa.

Ràng buộc

• 1 <= n <= 2 * 10^5
• 1 <= a < b <= 10^9

Chấm điểm

Ví dụ 1

Input

3
3 5
4 9
5 8

Output

2

Giải thích. Chọn [3,5) rồi [5,8).

Ví dụ 2

Input

4
1 10
2 3
3 4
4 5

Output

3

Giải thích. Bỏ phiên dài [1,10), chọn ba phiên ngắn liên tiếp.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Movie Festival (Task 1629).

Tham khảo: https://cses.fi/alon/task/1629