Công suất phục vụ cực đại

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

Một trung tâm dịch vụ ghi thời điểm bắt đầu và kết thúc của mỗi phiên sử dụng. Tất cả các thời điểm bắt đầu/kết thúc là phân biệt. Trung tâm cần biết số phiên đang hoạt động đồng thời lớn nhất để ước lượng công suất tối thiểu.

Yêu cầu

Tính số phiên hoạt động đồng thời lớn nhất tại bất kỳ thời điểm nào.

Input

• Dòng 1: n.
• n dòng: a b, với phiên bắt đầu tại a và kết thúc tại b.

Output

In số phiên đồng thời cực đại.

Ràng buộc

• 1 <= n <= 2 * 10^5
• 1 <= a < b <= 10^9
• Mọi thời điểm a và b đôi một phân biệt

Chấm điểm

Ví dụ 1

Input

3
5 8
2 4
3 9

Output

2

Giải thích. Trong khoảng sau thời điểm 3 và trước 4 có hai phiên; sau 5 và trước 8 cũng có hai.

Ví dụ 2

Input

4
1 2
3 4
5 6
7 8

Output

1

Giải thích. Các phiên không chồng lấn.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Restaurant Customers (Task 1619).

Tham khảo: https://cses.fi/problemset/task/1619