Attend the Most Events

Difficulty: 1800 5000 ms 128 MB

greedy heap

Each event spans days [start, end] and you can attend one event per day (any day within its span). Maximize the number of events attended.

Input: the first line has N; each of the next N lines has an event's start and end day.

Output: the maximum number of events attendable.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ start ≤ end ≤ 10⁵

Sample Tests

3
1 2
2 3
3 4

3

2
1 1
1 1

1

Read the Editorial