You are given n intervals, each written as [start, end) — half-open, including start but excluding end. Two intervals overlap when they share any point that lies strictly inside both; intervals that merely touch at an endpoint (one ends exactly where another begins) do not overlap and may both be chosen.
Select as many intervals as possible so that no two selected intervals overlap, and print the size of the largest such selection.
Line 1: an integer n, the number of intervals.
Next n lines: two space-separated integers start end describing one interval [start, end) with start < end.
When n = 0, no interval lines follow.
A single integer: the maximum number of pairwise non-overlapping intervals that can be chosen.
Example 1
Input
4 1 3 2 4 3 5 0 6
Expected
2
Explanation
Sorting by end gives [1,3), [2,4), [3,5), [0,6). Choosing [1,3) fixes the last end at 3; the next interval whose start is >= 3 is [3,5). Nothing further starts at or after 5, so the best selection has size 2.
Example 2
Input
3 1 2 2 3 3 4
Expected
3
Explanation
The intervals [1,2), [2,3), [3,4) each begin exactly where the previous one ends. Touching endpoints are allowed, so all three can be chosen and the answer is 3.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →