একটি সার্কেলে nটি গ্যাস স্টেশন আছে। প্রতিটি স্টেশনে গ্যাসের পরিমাণ এবং পরের স্টেশন পর্যন্ত দূরত্ব দেওয়া আছে। ১ ইউনিট গ্যাসে ১ ইউনিট দূরত্ব পার করা যায়। এমন একটি শুরুর পয়েন্ট বের করতে হবে যেখান থেকে গাড়ি পুরো সার্কেল পার করতে পারবে।
উদাহরণ: [(4,6), (6,5), (7,3), (4,5)] -> আউটপুট: start = 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
