Dsa
Greedy
Medium
Optimal Fuel Stations
You are on a long road trip and have a specific route to follow, represented as a straight line section from `0` to `n`. You can only make a stop at the fuel stations that are present along the route. Each fuel station has a certain distance from the starting point and can provide a fixed amount of fuel. Your goal is to determine the minimum number of fuel stations you need to visit to ensure you can travel the entire distance `n`. You must ensure that at any point, you have enough fuel to reach the next station or the final destination.
Input Format:
- The first line contains two integers, `n` (the total distance needed to cover) and `m` (the number of fuel stations).
- The next `m` lines each contain two integers: `d_i` (the distance of the i-th fuel station from the start) and `f_i` (the amount of fuel available at that station).
Output Format:
- Print a single integer representing the minimum number of fuel stations needed to reach the destination, or -1 if it is impossible.
Example:
Input:
10 3
2 5
4 3
6 2
Output:
2
Key concepts
greedyintervalsarrays
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now