Optimal Delivery Route with Fuel Constraints
Paytm's logistics division is optimizing package delivery routes. Drivers operate vehicles with limited fuel capacity and must make timely deliveries. This problem challenges you to find the most time-efficient route from a starting depot to a destination, accounting for fuel consumption, available fuel stations, and refueling times.
Implement a function findOptimalDeliveryTime that calculates the minimum total time required to travel from a startLocation to an endLocation.
travelTime and fuelConsumption.maxFuelCapacity and starts with initialFuel.fuelStation, the vehicle can refuel to full capacity. This process takes a fixed refuelTime.numLocations: An integer representing the total number of locations in the city (0 to numLocations-1).
roads: A 2D array of integers, where each road[i] = [u, v, travelTime, fuelConsumption] indicates a directed road from location u to location v. travelTime is the time taken to traverse this road, and fuelConsumption is the fuel consumed.
fuelStations: An array of integers, where each element is the index of a location that has a fuel station.
startLocation: An integer, the index of the starting depot.
endLocation: An integer, the index of the destination.
maxFuelCapacity: An integer, the maximum fuel the vehicle's tank can hold.
initialFuel: An integer, the initial amount of fuel in the vehicle's tank.
refuelTime: An integer, the fixed time taken to refuel to full capacity at any fuel station.
Return: An integer representing the minimum total time to reach the endLocation. Return -1 if the endLocation is unreachable.
travelTime, fuelConsumption, maxFuelCapacity, refuelTime values are positive integers (>= 1). initialFuel can be 0.initialFuel will not exceed maxFuelCapacity.startLocation or endLocation are also fuelStations.startLocation (i.e., initialFuel >= 0).Examples
Example 1
Input:
numLocations = 3, roads = [[0,1,10,5], [1,2,10,5]], fuelStations = [], startLocation = 0, endLocation = 2, maxFuelCapacity = 20, initialFuel = 15, refuelTime = 5
Output:
20
Note:
Path: 0 -> 1 (Time=10, Fuel=10) -> 2 (Time=20, Fuel=5). No refueling needed. Total time: 20.
Example 2
Input:
numLocations = 4, roads = [[0,1,10,10], [1,2,5,3], [2,3,10,10], [1,3,100,5]], fuelStations = [1], startLocation = 0, endLocation = 3, maxFuelCapacity = 10, initialFuel = 10, refuelTime = 2
Output:
112
Note:
Path 0 -> 1: Time=10, Fuel=0. At location 1 (fuel station), refuel. Time=10+2=12, Fuel=10. From 1 to 2 needs 3 fuel, then 2 to 3 needs 10 fuel (total 13), but we only have 10 fuel. So 1->2->3 is not possible. From 1 to 3: Time=12+100=112, Fuel=5. This is the optimal path.
Example 3
Input:
numLocations = 2, roads = [[0,0,1,1]], fuelStations = [], startLocation = 0, endLocation = 1, maxFuelCapacity = 10, initialFuel = 10, refuelTime = 1
Output:
-1
Note:
Location 1 is unreachable from location 0.
Constraints
1 <= numLocations <= 10000 <= roads.length <= 5000roads[i].length == 40 <= u, v < numLocations1 <= travelTime, fuelConsumption <= 10000 <= fuelStations.length <= numLocations0 <= startLocation, endLocation < numLocations1 <= maxFuelCapacity <= 2000 <= initialFuel <= maxFuelCapacity1 <= refuelTime <= 1000Loading editor...