एक्टिविटी सिलेक्शन प्रॉब्लम

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
    प्रारंभ में दी गई गतिविधि लिस्ट को सॉर्ट करें
    set i := 0
    ith गतिविधि प्रदर्शित करें // इस मामले में यह पहली गतिविधि है
    for j := 1 to n-1 do
        if act[j] का प्रारंभ समय >= act[i] का अंत तो
            jth गतिविधि प्रदर्शित करें
            i := j
        done
    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); // तुलना फंक्शन का उपयोग करके गतिविधियों को सॉर्ट करें
    cout << "चयनित गतिविधियाँ हैं: " << 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() {
    Activitiy actArr[] = {{5,9}, {1,2}, {3,4}, {0,6}, {5,7}, {8,9}};
    int n = 6;
    maxActivity(actArr, n);
    return 0;
}

आउटपुट

चयनित गतिविधियाँ हैं:
Activity: 0 , Start: 1 End: 2
Activity: 1 , Start: 3 End: 4
Activity: 3 , Start: 5 End: 7
Activity: 5 , Start: 8 End: 9