Minimum Number of Refueling Stops

Try to solve the Minimum Number of Refueling Stops problem.

Statement

You need to find the minimum number of refueling stops that a car needs to make to cover a distance, target. For simplicity, assume that the car has to travel from west to east in a straight line. There are various fuel stations on the way that are represented as a 2-D array of stations, i.e., stations[i] =[di,fi]= [d_i, f_i], where did_i is the distance (in miles) of the ithi^{th} gas station from the starting position, and fif_i is the amount of fuel (in liters) that it stores. Initially, the car starts with k liters of fuel. The car consumes one liter of fuel for every mile traveled. Upon reaching a gas station, the car can stop and refuel using all the petrol stored at the station. If it cannot reach the target, the program returns −1−1.

Note: If the car reaches a station with 00 fuel left, it can refuel from that station, and all the fuel from that station can be transferred to the car. If the car reaches the target with 00 fuel left, it is still considered to have arrived.

Constraints:

  • 1≤1 \leq target, k ≤109\leq 10^9
  • 0≤0 \leq stations.length ≤900\leq 900
  • 1≤di<di+1<1 \leq d_{i} < d_{i+1}< target
  • 1≤fi<1091 \leq f_{i} < 10^9

Examples

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy