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. In case it cannot reach the target, the program simply 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.

For example:

  • target: 1515
  • start fuel: 22
  • stations: [[1,2],[2,8],[4,10],[6,7],[7,2],[8,1]][[1, 2], [2, 8], [4, 10], [6, 7], [7, 2], [8, 1]]

If we want to reach the target of 15 miles, we have to refuel from a minimum of 22 stations to reach the target. First, we will refuel our car with 88 liters from the second station and then refuel 1010 liters from the third station.

Constraints:

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

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.