#757
Set Intersection Size At Least Two
expert · 1235 · lc hard +32 · verified · 57.9% accepted · 1,121 likes · top 54%
Description
Given a 2D integer array intervals where each intervals[i] = [starti, endi] covers all integers from starti to endi inclusively, find the smallest set of integers such that every interval contains at least two elements of the set. Return the size of this minimum set.
Example 1:
Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5
Explanation: let nums = [2, 3, 4, 8, 9].
It can be shown that there cannot be any containing array of size 4.
Example 2:
Input: intervals = [[1,3],[1,4],[2,5],[3,5]]
Output: 3
Explanation: let nums = [2, 3, 4].
It can be shown that there cannot be any containing array of size 2.
Example 3:
Input: intervals = [[1,2],[2,3],[2,4],[4,5]]
Output: 5
Explanation: let nums = [1, 2, 3, 4, 5].
It can be shown that there cannot be any containing array of size 4.
Code
1
2
3