FunctionRacerProblemsRace

Fewest Routers for a Corridor

MediumGreedyPython, JavaScript, TypeScript, Java, C++

A corridor runs from position 0 to position length. Each item of routers is [left, right]: that router gives signal to every point from left to right, both included. Choose the fewest routers so that every point of the corridor from 0 to length gets signal from at least one chosen router. Think of the corridor as a continuous line: [0, 4] and [5, 10] leave the stretch between 4 and 5 without signal, while [0, 4] and [4, 9] together cover everything from 0 to 9.

Return that fewest number of routers, or -1 if no choice of routers covers the whole corridor. Routers may be listed in any order and may reach beyond the corridor.

Example 1

length 10
routers [[0,4],[3,8],[4,10],[7,9]]
returns 2

[0, 4] is the only router covering 0; after it, [4, 10] reaches the end. Two routers.

Example 2

length 5
routers [[0,2],[3,5]]
returns -1

Nothing covers the stretch between 2 and 3, so the corridor cannot be covered.

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