Paper strips lie on a ruler; strip [a, b) covers the integer positions a, a + 1, ..., b - 1. A pin pushed through integer position x pierces every strip with a <= x < b. Return the minimum number of pins needed so that every strip is pierced at least once.
Examples
Input: strips = [[1, 4], [2, 6], [5, 7], [7, 9]]
Output: 3
Explanation: Pins at 3, 6 and 8. [1, 4) and [5, 7) share no position, and [7, 9) starts where [5, 7) stops.
Input: strips = [[0, 10], [3, 4], [8, 9]]
Output: 2
Explanation: Pins at 3 and 8; the long strip is hit by both.
Constraints
0 <= len(strips) <= 5 * 10**4,0 <= a < b <= 10**9(integers).- Half-open:
[1, 3)and[3, 5)cannot be pierced by one pin. - Target complexity: O(n log n).
Goals
- Choose the greedy pin position that keeps the most later strips reachable
- Handle half-open strips where touching strips need separate pins