Frontend School

Optimal Delivery Route with Fuel Constraints

DSA
hard

Optimal Delivery Route with Fuel Constraints

Hard
Graph
Shortest Path
Dijkstra
State Space Search

Overview

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.

What you need to do / Task

Implement a function findOptimalDeliveryTime that calculates the minimum total time required to travel from a startLocation to an endLocation.

  1. Model the city as a graph where locations are nodes and roads are directed edges.
  2. Each road has a travelTime and fuelConsumption.
  3. The vehicle has a fixed maxFuelCapacity and starts with initialFuel.
  4. At any location designated as a fuelStation, the vehicle can refuel to full capacity. This process takes a fixed refuelTime.
  5. If the destination is unreachable, return -1.

Input & output

  • 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.

Clarifications

  • All travelTime, fuelConsumption, maxFuelCapacity, refuelTime values are positive integers (>= 1). initialFuel can be 0.
  • initialFuel will not exceed maxFuelCapacity.
  • It is possible that startLocation or endLocation are also fuelStations.
  • Fuel consumption is exact; no partial fuel units.
  • You can assume there's enough fuel to start the journey from startLocation (i.e., initialFuel >= 0).

Examples

1

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.

2

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.

3

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

Constraints & assumptions

  • 1 <= numLocations <= 1000
  • 0 <= roads.length <= 5000
  • roads[i].length == 4
  • 0 <= u, v < numLocations
  • 1 <= travelTime, fuelConsumption <= 1000
  • 0 <= fuelStations.length <= numLocations
  • 0 <= startLocation, endLocation < numLocations
  • 1 <= maxFuelCapacity <= 200
  • 0 <= initialFuel <= maxFuelCapacity
  • 1 <= refuelTime <= 1000
  • The graph may contain self-loops or multiple edges between the same two locations. Consider all valid paths.

Out of scope

  • Handling negative travel times or fuel consumptions.
  • Dynamic changes to road conditions or fuel prices.
  • Optimizing for multiple vehicles or multiple packages.

What interviewers evaluate

  • Correctness of the shortest path algorithm adaptation to handle fuel constraints.
  • Efficient state representation and priority queue usage.
  • Handling of edge cases such as unreachable destinations or insufficient initial fuel for the first segment.
  • Code structure, readability, and adherence to best practices.

Loading editor...