Frontend School

Minimum Journey Refills

DSA
medium

Minimum Journey Refills

Medium
Greedy
Heap
Priority Queue

Overview

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.

What you need to do / Task

Implement the minRefills function that determines the minimum number of refills required to reach the target distance.

  1. Calculate the minimum number of times you need to refuel your car.
  2. If it's impossible to reach the destination, return -1.

Input & output

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.
    • The stations array is guaranteed to be sorted by distance in ascending order.

The function should return:

  • A number representing the minimum refills needed.
  • -1 if the destination cannot be reached.

Clarifications

  • You start at distance 0.
  • Fuel consumption is 1 unit of fuel per 1 unit of distance traveled.
  • You can only refuel at stations you have reached.
  • When you refuel at a station, you take the available fuel and add it to your tank. Your tank can store an arbitrarily large amount of fuel; there is no upper capacity limit after starting.

Examples

1

Example 1

Input:

targetDistance = 100, initialFuel = 10, stations = [[10, 60], [20, 30], [30, 30], [60, 40]]

Output:

2

Note:

  1. Start: currPos = 0, currFuel = 10, refills = 0.
  2. Drive to Station 1 [10, 60]: dist = 10. currFuel (10) >= 10. Arrive with 0 fuel. Add 60 to heap. heap=[60]. lastStopPos = 10.
  3. Drive to Station 2 [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.
  4. Drive to Station 3 [30, 30]: dist = 10. currFuel (50) >= 10. Arrive with 40 fuel. Add 30 to heap. heap=[60, 30, 30]. lastStopPos = 30.
  5. Drive to Station 4 [60, 40]: dist = 30. currFuel (40) >= 30. Arrive with 10 fuel. Add 40 to heap. heap=[60, 40, 30, 30]. lastStopPos = 60.
  6. Drive to Target [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.
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.

3

Example 3

Input:

targetDistance = 200, initialFuel = 50, stations = [[50, 20], [100, 10], [150, 10]]

Output:

-1

Note:

  1. Start: currPos = 0, currFuel = 50, refills = 0.
  2. Drive to Station 1 [50, 20]: dist = 50. currFuel (50) >= 50. Arrive with 0 fuel. Add 20 to heap. heap=[20]. lastStopPos = 50.
  3. Drive to Station 2 [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

Constraints & assumptions

  • 1 <= targetDistance <= 10^9
  • 0 <= initialFuel <= 10^9
  • 0 <= stations.length <= 10^5
  • For each [distance, fuel] in stations:
    • 0 < distance < targetDistance
    • 1 <= fuel <= 10^9
  • All station distances are unique and sorted in strictly ascending order.
  • The car consumes 1 unit of fuel per 1 unit of distance traveled.

What interviewers evaluate

  • Correctness of Greedy Strategy: Ability to identify and implement the optimal greedy choice for refueling.
  • Data Structure Usage: Effective application of a max-heap (priority queue) to manage available fuel from past stations.
  • Edge Case Handling: Robustness of the solution for scenarios like no stations, sufficient initial fuel, or impossible journeys.
  • Efficiency: Solution demonstrates optimal time and space complexity for the given constraints.

Loading editor...