FunctionRacerProblemsRace

Two From Every Interval

HardGreedyPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Greedy problems