Minimum Number of Refueling Stops

HardHeapheap

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A car drives east from position 0 toward a destination target miles away. It starts with startFuel liters in an unlimited tank and burns exactly one liter per mile. Along the way are gas stations: stations[i] = [position_i, fuel_i] means a station position_i miles from the start that holds fuel_i liters. If the car reaches a station it may stop and take all of that station's fuel. Reaching a station or the target with exactly 0 fuel left still counts as reaching it. Return the minimum number of refueling stops needed to reach target, or -1 if it is impossible. Aim for O(n log n).

Examples

Input: target = 1, startFuel = 1, stations = []
Output: 0
The starting fuel is enough.
Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
The car runs dry after 1 mile, before the first station.
Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Refuel at mile 10 (fuel becomes 60) and at mile 60 (fuel becomes 40), which is enough for the last 40 miles.

Constraints

  • 1 <= target, startFuel <= 10^9
  • 0 <= stations.length <= 500
  • 1 <= position_1 < position_2 < ... < position_n < target
  • 1 <= fuel_i <= 10^9

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More heap problems