Minimum Number of Refueling Stops LeetCode solution in C++

1
/*
2

3
The approach here used is - first cosider the stations which are possible at a
4
particular time and then take the one with maximum fuel that can be filled this
5
ensure that with only one fill up the vehicle will move to furthest distance.
6

7
Now there might be case where if we don't fill up from multiple stations ata
8
paritcular time, then it will not be possible to reach end as there might not be
9
any stations at the ending side of the target.
10

11
To handle above case, when such situation arise then we need to take the next
12
max fuel refill that is pissible from the already seen stations. Like this way
13
keep on taking fuels from stations in decreasing manner.
14

15
If at any point of time the queue is empty then, it means we do not have
16
sufficent fuel to reach target.
17

18
=> This logic can be implemented by simply using a priority queue where the max
19
fuel station is at top of the queue.
20

21

22
*/
23

24
class Solution {
25
 public:
26
  int minRefuelStops(int target, int startFuel, vector<vector<int>> &stations) {
27
    auto comp = [](vector<int> a, vector<int> b) { return a[1] < b[1]; };
28
    priority_queue<vector<int>, vector<vector<int>>, decltype(comp)> pq(comp);
29
    int i = 0, distance = startFuel, refillCount = 0;
30
    while (distance < target) {
31
      while (i < stations.size() && distance >= stations[i][0]) {
32
        pq.push(stations[i++]);
33
      }
34
      if (pq.empty()) return -1;
35
      distance += pq.top()[1];
36
      refillCount++;
37
      pq.pop();
38
    }
39
    return refillCount;
40
  }
41
};