তাদের শুরুর সময় এবং শেষের সময় সহ বিভিন্ন কার্যক্রম দেওয়া আছে। একক ব্যক্তির দ্বারা সমাধান করার জন্য সর্বাধিক সংখ্যক ক্রিয়াকলাপ নির্বাচন করুন৷
আমরা পরবর্তী ক্রিয়াকলাপটি খুঁজে পেতে লোভনীয় পদ্ধতি ব্যবহার করব যার শেষ সময়টি বিশ্রামের ক্রিয়াকলাপের মধ্যে সর্বনিম্ন এবং শুরুর সময়টি শেষ নির্বাচিত কার্যকলাপের সমাপ্তির সময়ের চেয়ে বেশি বা সমান৷
-
এই সমস্যার জটিলতা হল 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
অ্যালগরিদম
ম্যাক্সঅ্যাক্টিভিটি(অ্যাক্ট, সাইজ)
ইনপুট - কার্যকলাপের একটি তালিকা, এবং তালিকায় উপাদানের সংখ্যা।
আউটপুট - কার্যক্রমের ক্রম কিভাবে নির্বাচন করা হয়েছে।
Begin initially sort the given activity List set i := 1 display the i-th activity //in this case it is the first activity for j := 1 to n-1 do if start time of act[j] >= end of act[i] then display the jth activity i := j done End
উদাহরণ
#include<iostream>
#include<algorithm>
using namespace std;
struct Activitiy {
int start, end;
};
bool comp(Activitiy act1, Activitiy act2) {
return (act1.end < act2.end);
}
void maxActivity(Activitiy act[], int n) {
sort(act, act+n, comp); //sort activities using compare function
cout << "Selected Activities are: " << endl;
int i = 0;// first activity as 0 is selected
cout << "Activity: " << i << " , Start: " <<act[i].start << " End: " << act[i].end <<endl;
for (int j = 1; j < n; j++) { //for all other activities
if (act[j].start >= act[i].end) { //when start time is >=end time, print the activity
cout << "Activity: " << j << " , Start: " <<act[j].start << " End: " << act[j].end <<endl;
i = j;
}
}
}
int main() {
Activitiy 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
