Marathon Gel Stops

Fewest resource additions to reach a target from position and amount arrays

MediumHeapGreedy

A marathon organizer models a runner's energy using whole-number units. Traveling one meter consumes one energy unit. The runner starts at meter 0 with initial energy and must reach the finish at meter target.

There are aid stations at the strictly increasing positions in positions. Station i offers one gel pack that adds supplies[i] energy. The runner may either take that entire pack or pass the station without taking it. Each pack can be taken only once, and there is no upper limit on stored energy.

Energy must never become negative. Reaching a station or the finish with exactly zero energy is allowed, and a pack can be taken immediately upon reaching its station.

Return the minimum number of stations at which the runner must take a pack to reach the finish. Return -1 if reaching the finish is impossible.

Examples

Example 1

Input: positions = [2,4,7], supplies = [1,6,2], initial = 4, target = 10
Output: 1

The runner can reach the station at meter 4 using the starting energy. Taking its pack provides enough energy to reach the finish, so no other pack is needed.

Example 2

Input: positions = [3,8], supplies = [5,4], initial = 3, target = 12
Output: 2

The runner must take the first pack to reach the second station, then take the second pack to reach the finish. Skipping either pack prevents completion.

Example 3

Input: positions = [5,9], supplies = [20,20], initial = 4, target = 15
Output: -1

The starting energy is insufficient to reach the first station, so none of the available packs can help.

Constraints

  • 0 <= positions.length <= 3000
  • supplies.length == positions.length
  • 1 <= target <= 1000000
  • 0 <= initial <= 1000000
  • 0 < positions[i] < target
  • positions is strictly increasing
  • 1 <= supplies[i] <= 1000000

The intended complexity is O(n log n) time and O(n) auxiliary space, where n is the number of stations. All distances and energy amounts are exact integers.

Hints

Show hint 1

When the next location is out of reach, which pack from the stations already reached would extend your reach the most?

Show hint 2

Keep all available but unused packs in a max-heap. Only select a pack when more energy is necessary.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How could you also return the indices of the stations selected by your algorithm, in increasing order?
  • Would the same greedy strategy remain valid if stored energy had a fixed capacity?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem