সমস্যা বিবরণ
টার্গেট দূরত্ব t, প্রাথমিক ফুয়েল startFuel, এবং গ্যাস স্টেশনের তালিকা (পজিশন, ফুয়েল) দেওয়া থাকলে। গাড়ি ১ মাইল প্রতি ১ লিটার ফুয়েল খরচ করে। ন্যূনতম কতবার রি-ফিউয়েল করতে হবে টার্গেটে পৌঁছানোর জন্য? অসম্ভব হলে -1।
উদাহরণ
Target = 100, startFuel = 10, stations = [[10,40],[20,30],[30,20],[60,40]] → আউটপুট = 3
সমাধান পদ্ধতি
- গ্রিডি + প্রায়ориটি কিউ (Max Heap) ব্যবহার করা হয়।
- বর্তমান ফুয়েল দিয়ে যতদূর যাওয়া যায়, পথের স্টেশনগুলো পিকিউতে রাখা হয়।
- ফুয়েল চুকলে পিকিউ থেকে সর্বোচ্চ ফুয়েল নেওয়া হয়।
- স্টেশন খালি হলে -1 রিটার্ন।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minRefuelStops(int target, int fuel, vector<vector<int>> &st) {
sort(st.begin(), st.end());
priority_queue<int> pq;
int i = 0, 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
