मान लीजिए कि एक वृत्त है, और वृत्त पर n गैस स्टेशन हैं। हमारे पास डेटा के दो सेट हैं जैसे -
- हर गैस स्टेशन में जितनी गैस होती है
- एक गैस स्टेशन से दूसरे गैस स्टेशन की दूरी।
पहले बिंदु की गणना करें, जहां से एक कार सर्कल को पूरा करने में सक्षम होगी। 1 यूनिट गैस के लिए मान लें, कार 1 यूनिट दूरी तक जा सकती है। मान लीजिए कि चार गैस स्टेशन हैं, और गैस की मात्रा, और अगले गैस स्टेशनों से दूरी इस प्रकार है [(4, 6), (6, 5), (7, 3), (4, 5)], पहला बिंदु जहां से कार एक गोलाकार यात्रा कर सकती है, दूसरा गैस स्टेशन है। आउटपुट प्रारंभ होना चाहिए =1 (दूसरे गैस स्टेशनों का सूचकांक)
क्यू का उपयोग करके इस समस्या को कुशलता से हल किया जा सकता है। कतार का उपयोग वर्तमान दौरे को संग्रहीत करने के लिए किया जाएगा। हम पहले गैस स्टेशनों को कतार में सम्मिलित करेंगे, हम गैस स्टेशनों को तब तक सम्मिलित करेंगे जब तक हम या तो यात्रा पूरी नहीं कर लेते, या गैस की वर्तमान मात्रा नकारात्मक हो जाती है। यदि राशि ऋणात्मक हो जाती है, तो हम गैस स्टेशनों को खाली होने तक हटाते रहते हैं।
उदाहरण
एक बेहतर समझ प्राप्त करने के लिए आइए निम्नलिखित कार्यान्वयन को देखें -
#include <iostream>
using namespace std;
class gas {
public:
int gas;
int distance;
};
int findStartIndex(gas stationQueue[], int n) {
int start_point = 0;
int end_point = 1;
int curr_gas = stationQueue [start_point].gas - stationQueue [start_point].distance;
while (end_point != start_point || curr_gas < 0) {
while (curr_gas < 0 && start_point != end_point) {
curr_gas -= stationQueue[start_point].gas - stationQueue [start_point].distance;
start_point = (start_point + 1) % n;
if (start_point == 0)
return -1;
}
curr_gas += stationQueue[end_point].gas - stationQueue [end_point].distance;
end_point = (end_point + 1) % n;
}
return start_point;
}
int main() {
gas gasArray[] = {{4, 6}, {6, 5}, {7, 3}, {4, 5}};
int n = sizeof(gasArray)/sizeof(gasArray [0]);
int start = findStartIndex(gasArray, n);
if(start == -1)
cout<<"No solution";
else
cout<<"Index of first gas station : "<<start;
} इनपुट
[[4, 6], [6, 5], [7, 3], [4, 5]]
आउटपुट
Index of first gas station : 1