Khách hàng nhà hàng

Trong một buổi họp với giám đốc của một chuỗi nhà hàng nổi tiếng, FullHouse Dev được đưa ra một bài toán thú vị về quản lý lượng khách. Giám đốc muốn biết cách xác định số lượng khách hàng tối đa có mặt cùng lúc trong nhà hàng của họ. Với kinh nghiệm phong phú trong việc xử lý dữ liệu, FullHouse Dev đã nhanh chóng bắt tay vào phân tích vấn đề.

Bài toán

FullHouse Dev được cung cấp thời gian đến và rời đi của \(n\) khách hàng trong một nhà hàng. Nhiệm vụ là xác định số lượng khách hàng tối đa có mặt trong nhà hàng tại bất kỳ thời điểm nào.

INPUT FORMAT:

• Dòng đầu tiên chứa một số nguyên \(n\): số lượng khách hàng.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\): thời gian đến và thời gian rời đi của một khách hàng.

OUTPUT FORMAT:

• In ra một số nguyên: số lượng khách hàng tối đa có mặt cùng lúc trong nhà hàng.

Ràng buộc:

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq a < b \leq 10^9\)
• Tất cả các thời gian đến và rời đi đều khác nhau.

Ví dụ

INPUT

3
5 8
2 4
3 9

OUTPUT

2

Giải thích

Trong ví dụ này, số lượng khách hàng tối đa trong nhà hàng tại một thời điểm là 2. Điều này xảy ra trong khoảng thời gian từ 3 đến 4, khi cả khách hàng thứ hai và thứ ba đều có mặt trong nhà hàng.

FullHouse Dev đã giải thích rằng bằng cách sử dụng cấu trúc dữ liệu và thuật toán phù hợp, họ có thể giúp giám đốc theo dõi số lượng khách hàng trong nhà hàng một cách hiệu quả, từ đó tối ưu hóa việc quản lý nguồn lực và nâng cao trải nghiệm của khách hàng.