Vấn đề lựa chọn hoạt động (Greedy Algo-1) trong C ++?

Có n hoạt động khác nhau được đưa ra với thời gian bắt đầu và thời gian kết thúc của chúng. Chọn số lượng hoạt động tối đa để một người giải quyết.

Chúng tôi sẽ sử dụng phương pháp tham lam để tìm hoạt động tiếp theo có thời gian kết thúc là tối thiểu trong số các hoạt động nghỉ ngơi và thời gian bắt đầu nhiều hơn hoặc bằng thời gian kết thúc của hoạt động đã chọn cuối cùng.

• Độ phức tạp của bài toán này là O (n log n) khi danh sách không được sắp xếp. Khi danh sách đã sắp xếp được cung cấp thì độ phức tạp sẽ là O (n).

Đầu vào

Danh sách các hoạt động khác nhau với thời gian bắt đầu và kết thúc.

{(5,9), (1,2), (3,4), (0,6), (5,7), (8,9)}

Đầu ra

Các hoạt động đã chọn là -

Activity: 0 , Start: 1 End: 2
Activity: 1 , Start: 3 End: 4
Activity: 3 , Start: 5 End: 7
Activity: 5 , Start: 8 End: 9

Thuật toán

maxActivity (hành động, kích thước)

Đầu vào - Một danh sách các hoạt động và số lượng các phần tử trong danh sách.
Đầu ra - Thứ tự của các hoạt động đã được chọn như thế nào.

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

Ví dụ

#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;
}

Đầu ra

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