मान लीजिए कि एक कार है, जो शुरुआती स्थिति से एक गंतव्य तक जाती है, जो शुरुआती स्थिति से t मील पूर्व में है।
अब रास्ते में कई गैस स्टेशन हैं। तो प्रत्येक स्टेशन [i] एक गैस स्टेशन का प्रतिनिधित्व करता है जो स्टेशन [i] [0] प्रारंभिक स्थिति से मील पूर्व में है, और उस स्टेशन में स्टेशन [i] [1] लीटर गैस है।
अगर कार एक अनंत आकार के गैस टैंक से शुरू होती है, जिसमें शुरू में ईंधन लीटर ईंधन शुरू होता है। यह हर 1 मील में 1 लीटर गैस का उपयोग करती है जिसे वह चलाती है।
जब कार एक गैस स्टेशन पर पहुँचती है, तो वह रुक सकती है और ईंधन भरवा सकती है, इसलिए अब यह स्टेशन से सभी गैस को कार में स्थानांतरित कर देती है। हमें यह पता लगाना होगा कि अपने गंतव्य तक पहुंचने के लिए कार को कितने कम से कम ईंधन भरने के स्टॉप बनाने चाहिए? यदि गंतव्य तक पहुंचना असंभव है, तो -1 लौटें।
इसलिए, यदि इनपुट टारगेट =100, स्टार्टफ्यूएल =20, स्टेशन =[10,40], [20,30], [30,20], [60,40] जैसा है, तो आउटपुट 3 होगा। तो शुरू में 10 लीटर गैस है, पहले स्टेशन पर पहुंचने के बाद 40 लीटर गैस ट्रांसफर करेगी, इसलिए वर्तमान में (0 + 40) =40 लीटर गैस है, फिर तीसरे स्टेशन पर पहुंचें अब 20 लीटर गैस ट्रांसफर करें, इसलिए करंट मात्रा (20+20) =40 है, तो अंतिम स्टेशन पर पहुंचें, 40 लीटर गैस लें, इसलिए वर्तमान मात्रा (10 + 40) =50, अब तक हमने 60 मील की दूरी तय की है, इसलिए हमें पहुंचने के लिए 40 मील और जाना होगा गंतव्य, लक्ष्य तक पहुंचने के लिए पर्याप्त गैस है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
वर्तमान:=0
-
सरणी सेंट को सॉर्ट करें
-
प्राथमिकता कतार pq परिभाषित करें
-
मैं:=0, सीएनटी:=0
-
curr :=curr + फ्यूल
-
जबकि curr
-
(cnt 1 से बढ़ाएँ)
-
जबकि (i
-
pq में st[i, 1] डालें
-
(i 1 से बढ़ाएँ)
-
-
अगर pq खाली है, तो -
-
लूप से बाहर आएं
-
-
curr :=curr + pq का शीर्ष तत्व
-
pq से तत्व हटाएं
-
-
वापसी (यदि curr>=लक्ष्य, तो cnt, अन्यथा -1)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{10,40},{20,30},{30,20},{60,40}};
cout << (ob.minRefuelStops(100, 10, v));
} इनपुट
100, 10, {{10,40},{20,30},{30,20},{60,40}} आउटपुट
3