diff options
Diffstat (limited to 'other/min_num_refueling_stops.cpp')
-rw-r--r-- | other/min_num_refueling_stops.cpp | 22 |
1 files changed, 22 insertions, 0 deletions
diff --git a/other/min_num_refueling_stops.cpp b/other/min_num_refueling_stops.cpp new file mode 100644 index 0000000..34d929b --- /dev/null +++ b/other/min_num_refueling_stops.cpp @@ -0,0 +1,22 @@ +#include "leetcode.h" + +class Solution { +public: + int minRefuelStops(int target, int startFuel, vector<vector<int>> &stations) { + int n = stations.size(), ans = 0; + priority_queue<int> pq; + for (int i = 0; i <= n; i++) { + int dist = i == n ? target : stations[i][0]; + while (startFuel < dist) { + if (!pq.size()) + return -1; + startFuel += pq.top(); + ans++; + pq.pop(); + } + if (i < n) + pq.push(stations[i][1]); + } + return ans; + } +}; |