-
Notifications
You must be signed in to change notification settings - Fork 2
/
MinimumNumberOfRefuelingStops.java
94 lines (84 loc) · 3.47 KB
/
MinimumNumberOfRefuelingStops.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package Leetcode;
import java.util.PriorityQueue;
/**
* @author kalpak
*
* A car travels from a starting position to a destination which is target miles east of the starting position.
*
* Along the way, there are gas stations. Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas.
*
* The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses 1 liter of gas per 1 mile that it drives.
*
* When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.
*
* What is the least number of refueling stops the car must make in order to reach its destination? If it cannot reach the destination, return -1.
*
* Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there.
* If the car reaches the destination with 0 fuel left, it is still considered to have arrived.
*
*
* Example 1:
* Input: target = 1, startFuel = 1, stations = []
* Output: 0
* Explanation: We can reach the target without refueling.
*
* Example 2:
* Input: target = 100, startFuel = 1, stations = [[10,100]]
* Output: -1
* Explanation: We can't reach the target (or even the first gas station).
*
* Example 3:
* Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
* Output: 2
* Explanation:
* We start with 10 liters of fuel.
* We drive to position 10, expending 10 liters of fuel. We refuel from 0 liters to 60 liters of gas.
* Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
* and refuel from 10 liters to 50 liters of gas. We then drive to and reach the target.
* We made 2 refueling stops along the way, so we return 2.
*
*
* Note:
*
* 1 <= target, startFuel, stations[i][1] <= 10^9
* 0 <= stations.length <= 500
* 0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target
*/
public class MinimumNumberOfRefuelingStops {
public static int minRefuelStops(int target, int startFuel, int[][] stations) {
if (startFuel >= target)
return 0;
int currentFuel = startFuel;
int result = 0;
PriorityQueue<Integer> maxFuelHeap = new PriorityQueue<>((a, b) -> b - a);
for(int[] station : stations) {
int distance = station[0];
int stationGas = station[1];
while(currentFuel < distance) {
// If we cannot reach this distance with our currentFuel status, we should have refilled
// We greedily refill from the station with the most litres of gas
if(maxFuelHeap.isEmpty())
return -1;
currentFuel += maxFuelHeap.poll();
result++;
}
// push the current gas station into the heap for future reference
maxFuelHeap.offer(stationGas);
}
// All the stations have been reached.
// Need to check if we have reached the target or not
while(currentFuel < target) {
if(maxFuelHeap.isEmpty())
return -1;
currentFuel += maxFuelHeap.poll();
result++;
}
return result;
}
public static void main(String[] args) {
int[][] stations = new int[][]{{10,60},{20,30},{30,30},{60,40}};
int target = 100;
int startFuel = 10;
System.out.println(minRefuelStops(target, startFuel, stations));
}
}