Bài toán chọn hoạt động (Thuật toán tham lam) trong C++?

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

Chúng ta 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 nhỏ nhất trong các hoạt động còn lại, và thời gian bắt đầu lớn hơn hoặc bằng thời gian kết thúc của hoạt động vừa chọn.

• Độ phức tạp là O(n log n) khi danh sách chưa sắp xếp. Khi danh sách đã sắp xếp, độ phức tạp là O(n).

Đầu vào

Danh sách các hoạt động 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 được chọn:

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ố lượng phần tử.
Đầu ra - Thứ tự các hoạt động được chọn.

Bắt đầu
  ban đầu sắp xếp danh sách hoạt động
  đặt i := 1
  hiển thị hoạt động thứ i // trường hợp này là hoạt động đầu tiên
  for j := 1 đến n-1 thực hiện
    nếu thời gian bắt đầu của act[j] >= kết thúc của act[i] thì
      hiển thị hoạt động thứ j
      i := j
    done
Kết thúc

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); // sắp xếp hoạt động dùng hàm so sánh
  cout << "Selected Activities are: " << endl;
  int i = 0; // hoạt động đầu tiên là 0 được chọn
  cout << "Activity: " << i << " , Start: " << act[i].start << " End: " << act[i].end << endl;
  for (int j = 1; j < n; j++) { // cho tất cả hoạt động khác
    if (act[j].start >= act[i].end) { // khi thời gian bắt đầu >= kết thúc, in hoạt động
      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;
}

Kết quả

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