Each meeting has a start and end time. One room can hold one meeting at a time; a meeting may start exactly when the previous one ends. Print the largest number of meetings the room can host.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ start < end ≤ 10^9
Input and output
- Input
- Line 1: n Next n lines: start end
- Output
- One integer.
Examples
Input 1
4
1 3
2 4
3 5
6 7Output
31-3, 3-5, 6-7
Input 2
3
1 10
2 3
4 5Output
2Short meetings win.
Show hints
- Which meeting should go first to leave the most room afterwards?
Show the explanation
Sort meetings by end time and greedily take each one that starts at or after the end of the last meeting taken. Choosing the earliest-finishing meeting never hurts: any optimal schedule can swap its first meeting for this one. O(n log n) time.
Original UniCircle question. Last reviewed 21 Oct 2026.