Linear Warehouse Drone Delivery
Learn this problem
Capital OneINTERNOAProblem statement
You are designing a delivery system that uses drones in a linear warehouse. The warehouse is a number line that starts at position 0 and ends at position target.
Charging stations are placed at the positions in stations. A fully charged drone can carry the cargo at most 10 units to the right. For example, a drone launched at position 12 can reach any position through 22, inclusive, but cannot reach position 23.
Starting with the cargo at position 0, repeat this protocol until it reaches target:
- Carry the cargo on foot from its current position to the nearest charging station at or ahead of that position. If there is no such station before the target, carry the cargo directly to
target. - Launch a fully charged drone from that station and send the cargo as far as possible toward
target, up to10units. - If the target has not been reached, walk to the position where the drone landed, retrieve the cargo, and repeat.
Return the total distance over which the cargo is carried on foot. Walking performed without the cargo is not included.
Function
solution(target: int, stations: int[]) → intExamples
Example 1
target = 23stations = [7,4,14]return = 4Carry the cargo from 0 to station 4, adding 4. The drone carries it to 14. A drone can then launch from station 14 and reach 23, so no more cargo-carrying on foot is needed.
Example 2
target = 25stations = [20,10,0]return = 0The cargo begins at station 0. Drones launched from stations 0, 10, and 20 carry it all the way to the target, so the cargo is never carried on foot.
Example 3
target = 28stations = [25,3]return = 15Carry the cargo 3 units to station 3, then the drone carries it to 13. Carry it another 12 units to station 25, whose drone reaches the target. The total is 3 + 12 = 15.
Constraints
1 ≤ target ≤ 10^90 ≤ stations.length ≤ 10^50 ≤ stations[i] ≤ target