Activity Selection Problem (ปัญหาเลือกกิจกรรม)

Activity Selection Problem เป็นปัญหาเลือกกิจกรรมจำนวนมากที่สุดที่ไม่ทับซ้อนกัน (Non-overlapping) โดยแต่ละกิจกรรมมี เวลาเริ่มต้น และ เวลาสิ้นสุด ใช้แนวคิด Greedy Algorithm

ความซับซ้อน (Complexity)

• Unsorted Input: O(n log n) (ต้องเรียงก่อน)
• Sorted Input: O(n)
• Space: O(1) เพิ่มเติม

กลยุทธ์ Greedy

เลือกกิจกรรมที่ จบเร็วที่สุด (Earliest Finish Time) แล้วเลือกกิจกรรมถัดไปที่เริ่มหลังกิจกรรมก่อนหน้าจบ

ตัวอย่างข้อมูล

Activities (start, end): {(5,9), (1,2), (3,4), (0,6), (5,7), (8,9)}

Sorted by end time: (1,2), (3,4), (0,6), (5,7), (5,9), (8,9)

Selected: (1,2) → (3,4) → (5,7) → (8,9)  // 4 กิจกรรม

อัลกอริทึม (Pseudocode)

maxActivity(activities, n)
  sort activities by end time ascending
  i = 0
  select activity i
  for j = 1 to n-1:
    if activities[j].start >= activities[i].end:
      select activity j
      i = j

ตัวอย่างโค้ด C++

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Activity {
    int start, end;
    int index;  // เก็บ index ต้นฉบับ
};

bool compare(Activity a, Activity b) {
    return a.end < b.end;
}

void maxActivity(Activity act[], int n) {
    sort(act, act + n, compare);

    cout << "Selected Activities:\n";
    int i = 0;
    cout << "Activity " << act[i].index << ": 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 " << act[j].index << ": Start " << act[j].start << ", End " << act[j].end << endl;
            i = j;
        }
    }
}

int main() {
    Activity acts[] = {{5,9,0}, {1,2,1}, {3,4,2}, {0,6,3}, {5,7,4}, {8,9,5}};
    int n = 6;
    maxActivity(acts, n);
}

ผลลัพธ์

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

คุณสมบัติ

• Optimal: Greedy ให้คำตอบเหมาะสมที่สุดเสมอสำหรับปัญหานี้
• Interval Scheduling: ปัญหาคล้ายกัน: Interval Scheduling Maximization
• Variations: Weighted Activity Selection (ต้องใช้ Dynamic Programming)

การประยุกต์ใช้

• จัดตารางห้องประชุม/ห้องเรียน
• CPU Task Scheduling
• Resource Allocation
• TV/Radio Program Scheduling