मान लीजिए एक कार है, जो एक प्रारंभिक स्थिति से एक गंतव्य तक यात्रा करती है जो प्रारंभिक स्थिति से t मील पूर्व में है।
रास्ते में कई गैस स्टेशन हैं। प्रत्येक station[i] एक गैस स्टेशन को दर्शाता है जो station[i][0] मील पूर्व में है, और जिसमें station[i][1] लीटर गैस है।
यदि कार अनंत आकार के गैस टैंक के साथ शुरू होती है, जिसमें शुरू में startFuel लीटर ईंधन होता है। यह प्रति मील 1 लीटर गैस का उपयोग करती है।
जब कार एक गैस स्टेशन पर पहुंचती है, तो वह रुककर ईंधन भर सकती है, स्टेशन से कार में सारी गैस ट्रांसफर हो जाती है। हमें वह न्यूनतम ईंधन भरने के स्टॉप की संख्या ढूंढनी है जो कार को अपने गंतव्य तक पहुंचने के लिए करने होंगे? यदि गंतव्य तक पहुंचना असंभव है, तो -1 वापस करें।
उदाहरण के लिए, यदि लक्ष्य = 100, startFuel = 20, stations = [[10,40],[20,30],[30,20],[60,40]], तो आउटपुट 3 होगा।
हल करने का दृष्टिकोण
हम एक लालची दृष्टिकोण का उपयोग करते हैं जिसमें मैक्स-हीप (प्रायोरिटी क्यू) होता है:
स्टेशन को स्थिति के अनुसार सॉर्ट करें
पहुंच योग्य स्टेशनों के ईंधन को मैक्स-हीप में डालें
जब वर्तमान ईंधन अगले स्टेशन/लक्ष्य तक पहुंचने के लिए अपर्याप्त हो, तो सबसे बड़े ईंधन वाले स्टेशन पर रुकें
स्टॉप गिनें जब तक लक्ष्य पहुंच योग्य न हो या हीप खाली न हो
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minRefuelStops(int target, int fuel, vector<vector<int>> &st) {
int curr = 0;
sort(st.begin(), st.end());
priority_queue<int> pq;
int i = 0;
int cnt = 0;
curr += fuel;
while (curr < target) {
cnt++;
while (i < st.size() && st[i][0] <= curr) {
pq.push(st[i][1]);
i++;
}
if (pq.empty()) break;
curr += pq.top();
pq.pop();
}
return curr >= target ? cnt : -1;
}
};
int main(){
Solution ob;
vector<vector<int>> v = {{10,40},{20,30},{30,20},{60,40}};
cout << (ob.minRefuelStops(100, 10, v));
return 0;
}
इनपुट
100, 10, {{10,40},{20,30},{30,20},{60,40}}
आउटपुट
3