Question bank › Greedy
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
Part of Praxari's verified interview question bank. We show the prompt and concepts to practise with — never a copy-paste solution.