The Busiest Moment

Difficulty: 1500 3000 ms 128 MB

intervals sorting

Each interval [a, b] marks when one guest is present (inclusive endpoints, integer time). What is the maximum number of guests present at the same moment?

Input: the first line has N; the next N lines each have two integers a b (a ≤ b).

Output: the maximum simultaneous count.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ a ≤ b ≤ 10⁶

Sample Tests

3
1 5
2 3
4 8

2

2
1 2
3 4

1

Read the Editorial