उनके शुरुआती समय और समाप्ति समय के साथ अलग-अलग गतिविधियां दी गई हैं। एक व्यक्ति द्वारा हल की जाने वाली गतिविधियों की अधिकतम संख्या चुनें।
हम अगली गतिविधि को खोजने के लिए लालची दृष्टिकोण का उपयोग करेंगे जिसका समापन समय बाकी गतिविधियों के बीच न्यूनतम है, और प्रारंभ समय अंतिम चयनित गतिविधि के समाप्ति समय से अधिक या बराबर है।
-
जब सूची को क्रमबद्ध नहीं किया जाता है तो इस समस्या की जटिलता ओ (एन लॉग एन) होती है। जब क्रमबद्ध सूची प्रदान की जाती है तो जटिलता 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