Vấn đề lựa chọn hoạt động

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 để giải quyết bởi một người. 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 vấ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, độ phức tạp sẽ là O (n).

Đầu vào và Đầu ra

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

Thuật toán

maxActivity(act, size)

Đầu vào: Danh sách hoạt động và số phần tử trong danh sách.

Đầu ra - Thứ tự của các hoạt động như thế nào chúng đã được chọn.

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

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