Two From Every Interval
Each entry of intervals is [start, end] and stands for all the whole numbers from start to end, both included.
Pick a set of whole numbers so that every interval contains at least two of the picked numbers. Return the size of the smallest such set.
Example 1
intervals [[1,4],[2,6],[5,8]]
returns 4
[1, 4] and [5, 8] share no number, so each needs two picks of its own. Picking 3, 4, 7 and 8 also covers [2, 6].
Example 2
intervals [[1,3],[3,5]]
returns 3
The two intervals only share the number 3. Picking 2, 3 and 5 works.
Example 3
intervals [[0,9],[3,5],[4,6]]
returns 2
The numbers 4 and 5 lie in all three intervals.
Constraints
1 <= len(intervals) <= 300 <= start < end <= 10**8
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Greedy problems
- Coins Handed BackBeginner
- Coins on the TableBeginner
- Fewest BanknotesBeginner
- Fewest JugsBeginner
- Greedy CoinsBeginner
- Least Total Waiting TimeBeginner
- Most Tasks in a Time BudgetBeginner
- Only the Best CountBeginner