n अलग-अलग एक्टिविटीज दी गई हैं जिनके प्रारंभ और समाप्ति समय हैं। एक व्यक्ति द्वारा हल की जा सकने वाली अधिकतम एक्टिविटीज चुनें।
हम लालची दृष्टिकोण का उपयोग करेंगे ताकि अगली एक्टिविटी ढूंढी जाए जिसका समाप्ति समय शेष एक्टिविटीज में न्यूनतम हो, और प्रारंभ समय अंतिम चयनित एक्टिविटी के समाप्ति समय से अधिक या बराबर हो।
इस समस्या की जटिलता 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)
इनपुट - एक्टिविटी की सूची, और सूची में तत्वों की संख्या।
आउटपुट - एक्टिविटीज का क्रम जिसमें उन्हें चुना गया है।
Begin
initially दी गई एक्टिविटी सूची को सॉर्ट करें
set i := 1
i-th एक्टिविटी प्रदर्शित करें // इस मामले में यह पहली एक्टिविटी है
for j := 1 to n-1 do
if act[j] का प्रारंभ समय >= act[i] का अंत तो
jth एक्टिविटी प्रदर्शित करें
i := j
end if
done
End
उदाहरण
#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
