You are given a list of closed intervals intervals where each intervals[i] = [start, end] satisfies start < end. A point x stabs an interval [start, end] if start <= x <= end.
Return the minimum number of points such that every interval is stabbed by at least one point.
Examples
Example 1
Input: intervals = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: A point at 6 stabs [2,8] and [1,6]; a point at 11 stabs [10,16] and [7,12].
Example 2
Input: intervals = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: No two intervals overlap, so each one needs its own point.
Example 3
Input: intervals = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: A point at 2 stabs [1,2] and [2,3]; a point at 4 stabs [3,4] and [4,5].
Constraints
1≤intervals.length≤105
−231≤start<end≤231−1 for each [start, end] in intervals
Examples
Example 1
Input
intervals = [[10, 16], [2, 8], [1, 6], [7, 12]]
Output
2
Example 2
Input
intervals = [[1, 2], [3, 4], [5, 6], [7, 8]]
Output
4
Example 3
Input
intervals = [[1, 2], [2, 3], [3, 4], [4, 5]]
Output
2
Loading editor...
Run checks the sample cases; Submit runs every case.
Samples 3
Custom 0
passedwrong answertime limiterrorran, no expected valuenot run