একটি স্টেশনে Nটি প্ল্যাটফর্ম (প্রতিটিতে ২ ট্র্যাক) এবং Tটি ট্রেন আছে। প্রতিটি ট্রেনের আগমন-প্রস্থান সময় ও প্ল্যাটফর্ম নম্বর দেওয়া আছে। সর্বোচ্চ কতটি ট্রেনকে স্টপেজ দেওয়া যাবে তা বের করতে হবে (গ্রিডি / এক্টিভিটি সিলেকশন)।
উদাহরণ
N = 3, T = 5
Trains = {{0915,0930,2}, {0930,0945,1}, {0930,1200,1}, {0910,0925,3}, {0940,1015,1}}
আউটপুট: 4
অ্যালগরিদম
- প্রতিটি প্ল্যাটফর্মের জন্য ট্রেনের লিস্ট বানান।
- প্রতিটি লিস্টকে ডিপারচার টাইম অনুযায়ী সর্ট করুন।
- এক্টিভিটি সিলেকশন: যেসব ট্রেন ওভারল্যাপ না করে সেগুলো বাছাই করুন।
C++ প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
int maxStop(int trains[][3], int N, int T) {
vector<pair<int,int>> tStopping[N+1];
for (int i = 0; i < T; i++)
tStopping[trains[i][2]].push_back({trains[i][1], trains[i][0]});
for (int i = 0; i <= N; i++)
sort(tStopping[i].begin(), tStopping[i].end());
int trainsStopped = 0;
for (int i = 0; i <= N; i++) {
if (tStopping[i].empty()) continue;
int a = 0;
trainsStopped++;
for (int j = 1; j < tStopping[i].size(); j++) {
if (tStopping[i][j].second >= tStopping[i][a].first) {
a = j;
trainsStopped++;
}
}
}
return trainsStopped;
}
int main() {
int N = 3, T = 5;
int trains[T][3] = {{915,930,2},{930,945,3},{930,1200,1},{910,925,3},{940,1015,1}};
cout << "Max trains stopped: " << maxStop(trains, N, T);
return 0;
}
আউটপুট: Max trains stopped: 4
