কার্যকলাপ নির্বাচন সমস্যা

এখানে বিভিন্ন ক্রিয়াকলাপ তাদের শুরুর সময় এবং শেষের সময় দেওয়া আছে৷ একক ব্যক্তির দ্বারা সমাধান করার জন্য সর্বাধিক সংখ্যক ক্রিয়াকলাপ নির্বাচন করুন। আমরা পরবর্তী ক্রিয়াকলাপটি খুঁজে পেতে লোভনীয় পদ্ধতি ব্যবহার করব যার শেষ সময়টি বিশ্রামের ক্রিয়াকলাপের মধ্যে সর্বনিম্ন এবং শুরুর সময়টি শেষ নির্বাচিত কার্যকলাপের সমাপ্তির সময়ের চেয়ে বেশি বা সমান৷

• এই সমস্যার জটিলতা হল O(n log n) যখন তালিকাটি সাজানো হয় না।
• যখন সাজানো তালিকা দেওয়া হয় তখন জটিলতা হবে O(n)।

ইনপুট এবং আউটপুট

Input:
A list of different activities with starting and ending times.
{(5,9), (1,2), (3,4), (0,6), (5,7), (8,9)}
Output:
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

অ্যালগরিদম

maxActivity(act, size)

ইনপুট: কার্যকলাপের একটি তালিকা, এবং তালিকায় উপাদানের সংখ্যা।

আউটপুট - ক্রিয়াকলাপের ক্রম কিভাবে তাদের বেছে নেওয়া হয়েছে।

Begin
   initially sort the given activity List
   set i := 1
   display the ith 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