← 返回 uber 的题目列表Minimum Number of Refueling Stops
类型：online_judge
Given a target position target, initial fuel startFuel, and a list of gas stations stations, return the minimum number of refueling stops needed to reach the target.
The car starts at position 0. It consumes one unit of fuel per unit of distance. At each station, you may either skip it or take all fuel available at that station. Each station can be used at most once.
Each station is represented as stations[i] = [position_i, fuel_i], and stations are sorted by strictly increasing position.
Return -1 if the target cannot be reached.
Input format
target startFuel
n
position_1 fuel_1
position_2 fuel_2
...
position_n fuel_n
Output format
The minimum number of refueling stops, or -1 if unreachable.
Constraints
1 <= target <= 10^9
0 <= startFuel <= 10^9
0 <= n <= 10^5
1 <= position_i < target
1 <= fuel_i <= 10^9
Example
Input
100 10
4
10 60
20 30
30 30
60 40
Output
2