অ্যাক্টিভিটি সিলেকশন সমস্যায় n সংখ্যক অ্যাক্টিভিটির স্টার্ট এবং এন্ড টাইম দেওয়া থাকে। একজনের জন্য সর্বোচ্চ সংখ্যক অ্যাক্টিভিটি সিলেক্ট করতে হয়। গ্রিডি অ্যাপ্রোচ: যে অ্যাক্টিভিটির ফিনিশ টাইম সবচেয়ে কম এবং স্টার্ট টাইম লাস্ট সিলেক্টেড অ্যাক্টিভিটির ফিনিশ টাইমের চেয়ে বড় বা সমান, সেটি বেছে নেওয়া হয়।
কমপ্লেক্সিটি
- অনসর্টেড লিস্ট: O(n log n)
- সর্টেড লিস্ট: O(n)
ইনপুট এবং আউটপুট
Input: {(5,9), (1,2), (3,4), (0,6), (5,7), (8,9)}
Output: Selected Activities:
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)
Input: অ্যাক্টিভিটি লিস্ট, সাইজ
Output: সিলেক্টেড অ্যাক্টিভিটির অর্ডার
Begin
act লিস্টকে এন্ড টাইম অনুযায়ী সর্ট করুন
i := 0 (প্রথম অ্যাক্টিভিটি সিলেক্ট)
display i-th activity
for j := 1 to n-1 do
if act[j].start >= act[i].end then
display j-th activity
i := j
done
done
End
C++ উদাহরণ
#include <iostream>
#include <algorithm>
using namespace std;
struct Activity { int start, end; };
bool comp(Activity a1, Activity a2) { return a1.end < a2.end; }
void maxActivity(Activity act[], int n) {
sort(act, act+n, comp);
cout << "Selected Activities are:" << endl;
int i = 0;
cout << "Activity: " << i << " , Start: " << act[i].start << " End: " << act[i].end << endl;
for(int j=1; j= act[i].end) {
cout << "Activity: " << j << " , Start: " << act[j].start << " End: " << act[j].end << endl;
i = j;
}
}
}
int main() {
Activity arr[] = {{5,9},{1,2},{3,4},{0,6},{5,7},{8,9}};
maxActivity(arr, 6);
}
আউটপুট
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
