n সংখ্যক ভিন্ন ক্রিয়া (activity) তাদের শুরু এবং সমাপ্তি সময়সহ দেওয়া আছে। একটি ব্যক্তি দ্বারা সর্বাধিক সংখ্যক ক্রিয়া সম্পন্ন করার পদ্ধতি খুঁজে বের করতে হবে।
আমরা লোভী (greedy) পদ্ধতি ব্যবহার করব: শेष ক্রিয়াগুলোর মধ্যে যেটির সমাপ্তি সময় ন্যূনতম এবং যার শুরু সময় শেষ নির্বাচিত ক্রিয়ার সমাপ্তি সময়ের চেয়ে বড় বা সমান, সেটি নির্বাচন করব।
- যদি তালিকা সর্ট করা না থাকে, জটিলতা O(n log n)। সর্ট করা থাকলে O(n)।
ইনপুট
শুরু এবং সমাপ্তি সময়সহ ক্রিয়ার তালিকা:
{(5,9), (1,2), (3,4), (0,6), (5,7), (8,9)}
আউটপুট
নির্বাচিত ক্রিয়াগুলো:
Activity: 0 , Start: 1 End: 2 Activity: 1 , Start: 3 End: 4 Activity: 3 , Start: 5 End: 7 Activity: 5 , Start: 8 End: 9
অ্যালগরিদম
maxActivity(act, size)
ইনপুট - ক্রিয়ার তালিকা এবং উপাদানের সংখ্যা।
আউটপুট - ক্রিয়াগুলো কীভাবে নির্বাচিত হয়েছে তার ক্রম।
শুরু
প্রাথমিকভাবে ক্রিয়া তালিকাটি সর্ট করুন
i := 1
i-তম ক্রিয়া প্রদর্শন করুন // এখানে প্রথম ক্রিয়া
j := 1 থেকে n-1 পর্যন্ত করুন
যদি act[j]-এর শুরু সময় >= act[i]-এর সমাপ্তি সময় হয়, তবে
j-তম ক্রিয়া প্রদর্শন করুন
i := j
শেষ করুন
শেষ
উদাহরণ কোড
#include <iostream>
#include <algorithm>
using namespace std;
struct Activity {
int start, end;
};
bool comp(Activity act1, Activity act2) {
return (act1.end < act2.end);
}
void maxActivity(Activity act[], int n) {
sort(act, act + n, comp); // তুলনা ফাংশন ব্যবহার করে সর্ট
cout << "Selected Activities are: " << endl;
int i = 0; // প্রথম ক্রিয়া 0 নির্বাচিত
cout << "Activity: " << i << " , Start: " << act[i].start << " End: " << act[i].end << endl;
for (int j = 1; j < n; j++) { // বাকি ক্রিয়াগুলোর জন্য
if (act[j].start >= act[i].end) { // শুরু সময় >= সমাপ্তি সময় হলে
cout << "Activity: " << j << " , Start: " << act[j].start << " End: " << act[j].end << endl;
i = j;
}
}
}
int main() {
Activity actArr[] = {{5,9},{1,2},{3,4},{0,6},{5,7},{8,9}};
int n = 6;
maxActivity(actArr, n);
return 0;
}
আউটপুট
Selected Activities are: Activity: 0 , Start: 1 End: 2 Activity: 1 , Start: 3 End: 4 Activity: 3 , Start: 5 End: 7 Activity: 5 , Start: 8 End: 9
