Minimum Journey Refills
You are embarking on an epic road trip and need to reach a distant destination. Your car starts with a certain amount of fuel. Along the way, there are several fuel stations, each located at a specific distance from your starting point and providing a fixed amount of fuel. Your primary goal is to reach the final destination, making sure you don't run out of fuel. To optimize your journey, you want to achieve this with the minimum possible number of refills.
Implement the minRefills function that determines the minimum number of refills required to reach the target distance.
The function signature is minRefills(targetDistance: number, initialFuel: number, stations: [number, number][]): number.
targetDistance: A number representing the total distance to your destination from the starting point (0).initialFuel: A number representing the amount of fuel in your tank at the start of the journey.stations: An array of arrays, where each inner array [distance, fuel] represents a fuel station.
distance: The distance of the station from the starting point (0).fuel: The amount of fuel available at this station.stations array is guaranteed to be sorted by distance in ascending order.The function should return:
number representing the minimum refills needed.-1 if the destination cannot be reached.Examples
Example 1
Input:
targetDistance = 100, initialFuel = 10, stations = [[10, 60], [20, 30], [30, 30], [60, 40]]
Output:
2
Note:
currPos = 0, currFuel = 10, refills = 0.[10, 60]: dist = 10. currFuel (10) >= 10. Arrive with 0 fuel. Add 60 to heap. heap=[60]. lastStopPos = 10.[20, 30]: dist = 10. currFuel (0) < 10. Need refill. Pop 60 from heap. currFuel = 0 + 60 = 60. refills = 1. currFuel (60) >= 10. Arrive with 50 fuel. Add 30 to heap. heap=[60, 30]. lastStopPos = 20.[30, 30]: dist = 10. currFuel (50) >= 10. Arrive with 40 fuel. Add 30 to heap. heap=[60, 30, 30]. lastStopPos = 30.[60, 40]: dist = 30. currFuel (40) >= 30. Arrive with 10 fuel. Add 40 to heap. heap=[60, 40, 30, 30]. lastStopPos = 60.[100, 0]: dist = 40. currFuel (10) < 40. Need refill. Pop 60 from heap. currFuel = 10 + 60 = 70. refills = 2. currFuel (70) >= 40. Arrive with 30 fuel. lastStopPos = 100.
Total refills: 2.Example 2
Input:
targetDistance = 100, initialFuel = 100, stations = [[20, 10], [50, 30], [70, 10]]
Output:
0
Note:
Starting with 100 fuel, you have enough to reach the destination (100 distance) without needing any refills. You will pass by stations, but you don't need to stop for fuel.
Example 3
Input:
targetDistance = 200, initialFuel = 50, stations = [[50, 20], [100, 10], [150, 10]]
Output:
-1
Note:
currPos = 0, currFuel = 50, refills = 0.[50, 20]: dist = 50. currFuel (50) >= 50. Arrive with 0 fuel. Add 20 to heap. heap=[20]. lastStopPos = 50.[100, 10]: dist = 50. currFuel (0) < 50. Need refill. Pop 20 from heap. currFuel = 0 + 20 = 20. refills = 1. Still currFuel (20) < 50. No more fuel options in heap. Impossible to reach station 2. Return -1.Constraints
1 <= targetDistance <= 10^90 <= initialFuel <= 10^90 <= stations.length <= 10^5[distance, fuel] in stations:
0 < distance < targetDistance1 <= fuel <= 10^9Loading editor...