Cho 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. Dùng tham lam (greedy): chọn hoạt động tiếp theo có thời gian kết thúc sớm nhất trong các hoạt động còn lại, và thời gian bắt đầu ≥ thời gian kết thúc của hoạt động vừa chọn.
- Độ phức tạp: O(n log n) nếu danh sách chưa sắp xếp.
- O(n) nếu danh sách đã sắp xếp theo thời gian kết thúc.
Input và Output
Input: Danh sách hoạt động (start, end):
{(5,9), (1,2), (3,4), (0,6), (5,7), (8,9)}
Output: 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)
Input: Danh sách hoạt động, số lượng
Output: Thứ tự hoạt động được chọn
Begin
sắp xếp act theo thời gian kết thúc tăng dần
i := 0
hiển thị hoạt động i (hoạt động đầu tiên)
for j := 1 to n-1 do
if start[act[j]] >= end[act[i]] then
hiển thị hoạt động j
i := j
done
done
End
Ví dụ (C++)
#include <iostream>
#include <algorithm>
using namespace std;
struct Activity { int start, end; };
bool comp(Activity a1, Activity a2) { return a1.end < a2.end; }
void maxActivity(Activity act[], int n) {
sort(act, act + n, comp);
cout << "Hoạt động được chọn:\n";
int i = 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() {
Activity act[] = {{5,9},{1,2},{3,4},{0,6},{5,7},{8,9}};
int n = 6;
maxActivity(act, n);
}
Kết quả
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
Chứng minh tối ưu: Chiến lược greedy chọn hoạt động kết thúc sớm nhất luôn để lại nhiều thời gian nhất cho các hoạt động sau. Đây là bài toán kinh điển của Greedy Algorithm.