814. Pair Chain
Each row of pairs holds two integers that mark the start and end times of a booth rental. The two numbers can come in either order; treat the smaller one as the start and the larger one as the end (they may be equal).
A chain is a sequence of rentals taken from the list, in any order of choosing, such that each rental starts strictly after the previous one in the chain has ended. Return the largest number of rentals in a chain. At least one rental can always be taken.
Aim for time O(n log n) and extra space O(n), where n is the number of rows.
Example 1
- Input:
- pairs = [[3,9],[10,4],[12,14],[20,15]]
- Output:
- 3
- Explanation:
Read low to high, the pairs [3,9], [12,14] and [15,20] link up in order; [4,10] overlaps [3,9].
Example 2
- Input:
- pairs = [[0,5],[2,7],[5,8],[9,9]]
- Output:
- 2
- Explanation:
[0,5] must end strictly before the next start, so [5,8] cannot follow it; [0,5] then [9,9] gives a chain of 2.
Constraints
1 ≤ pairs.length ≤ 20000
pairs[i].length == 2
-109 ≤ pairs[i][j] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)