Minimum Number of Refueling Stops

Given a destination, initial fuel and stations offering fixed fuel amounts, minimize how many stations you use. Assume one unit of fuel per distance and no tank-capacity limit. A max-heap of stations already within reach lets us defer a decision until more fuel is necessary, then select the largest available contribution. The heap decision is retroactive bookkeeping for a feasible journey, not permission to refuel at a station never reached.

Prerequisites: Priority Queues; sorting by eligibility; reach dominance.

Build the idea

1. Track maximum reachable distance

   Starting at position zero with initial fuel F, reach=F is the farthest coordinate possible with fuel already chosen. Sort stations by position. Before choosing another stop, insert every station at position≤reach into a max-heap. Such stations could have been visited during the journey supported by the existing choices. Ignore zero-fuel stations because they cannot extend reach.

2. Make a choice only when necessary

   If reach already meets target, stop without extra refueling. Otherwise take the largest fuel amount in the passed heap, add it to reach, and count one stop. If the heap is empty, no currently reachable station can extend the journey, so the target is impossible. Each station is inserted once and popped at most once.

   $$\mathrm{newReach}=\mathrm{reach}+\mathrm{largestPassedFuel}$$

3. Correctness proof: postpone and exchange

   Before more fuel is needed, postponing the commitment cannot reduce available choices. Among stations reachable without this extra stop, choosing the largest fuel reaches at least as far as choosing any other single station. Any competing next selected contribution can be exchanged with this one: the larger fuel preserves all subsequent reachable stations, and the displaced smaller contribution can be retained for later if needed. Repeating this reach-dominance exchange shows greedy never needs more selected stops than an optimum. This reasoning depends on unlimited tank capacity and station fuel being additive.

4. Trace the sample

   Target is 100 and initial reach 10. Station (10,60) is eligible and extends reach to 70, using one stop. Stations at 20,30,60 are now eligible, with fuel 30,30,40. Select 40 to reach 110, giving two stops. We do not need to stop at every passed station, and a station at 80 would not have been eligible before the first extension.

   Before stop	Eligible fuel	Chosen	New reach
   10	60	60	70
   70	30,30,40	40	110

5. Reconstruct physical meaning

   The selected stations can be visited in their physical position order. Every choice was within reach using previously selected fuel, so this reordering describes a realizable trip under the model. A fixed tank capacity breaks the simple additive reach state; fuel prices change the objective from stop count to cost and need another strategy. Stations beyond target are irrelevant and excluded by the input contract.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<utility>
int main(){
    int n;
    long long target,reach;
    std::cin>>n>>target>>reach;
    std::vector<std::pair<long long,long long>>station(n);
    for(auto&[position,fuel]:station){
        std::cin>>position>>fuel;
    }
    std::sort(station.begin(),station.end());
    std::priority_queue<long long>passed;
    int i=0,stops=0;
    while(reach<target){
        while(i<n&&station[i].first<=reach){
            if(station[i].second>0){
                passed.push(station[i].second);
            }
            ++i;
        }
        if(passed.empty()){
            std::cout<<"IMPOSSIBLE\n";
            return 0;
        }
        reach+=passed.top();
        passed.pop();
        ++stops; // Retroactively choose a reachable station; no tank-capacity limit.
    }
    std::cout<<stops<<'\n';
}

Complexity analysis

O(n log n) sorting and total heap work, O(n) station/heap storage. reach≤initialFuel+sum(fuel)≤1.00001·10^14, so long long avoids overflow even though positions fit int.

Example input and output

Read n target initialFuel (0≤n≤100000, target and initialFuel in 0..10^9), then n position fuel pairs with 0≤position≤target and 0≤fuel≤10^9. Tank capacity is unlimited. Print minimum stops or IMPOSSIBLE.

Input

4 100 10
10 60
20 30
30 30
60 40

Output

2

Fuel 60 at position 10 extends reach to 70; fuel 40 from position 60 then reaches 110.

Practical applications

Use for minimum additive resource boosts when candidates become eligible as reach expands and choices can be deferred. Similar heaps appear in project expansion, but negative contributions or prerequisites may require a different invariant.

Check your understanding

Which stations may enter the heap?

Put it into practice

Compare every station subset on a small route.