FunctionRacerProblemsRace

Circular Delivery Route

MediumGreedyPython, JavaScript, TypeScript, Java, C++

n depots sit on a circular route, numbered 0 to n - 1. Your van starts with an empty tank. On arriving at depot i (including the depot you start from) you collect fuel[i] litres, and driving from depot i to the next depot (i + 1, or depot 0 after depot n - 1) burns cost[i] litres. You may start at any depot and must drive the full loop back to it, and the tank may never go below 0 litres on the way. Return the smallest index of a depot from which the full loop is possible, or -1 if no depot works.

Example 1

fuel [1,2,3,4,5]
cost [3,4,5,1,2]
returns 3

From depot 3: collect 4, drive (tank 3), collect 5 (8), drive (6), collect 1 (7), drive (4), collect 2 (6), drive (2), collect 3 (5), drive home (0). Starting at 0, 1 or 2 runs the tank below 0.

Example 2

fuel [2,3,4]
cost [3,4,3]
returns -1

The depots give 9 litres in total but the loop burns 10, so no start can work.

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