ปัญหา Activity Selection (Greedy Algorithm) ใน C++

มีกิจกรรม n กิจกรรมที่กำหนดเวลาเริ่มต้นและเวลาสิ้นสุด ให้เลือกกิจกรรมสูงสุดที่คนเดียวสามารถทำได้ เราจะใช้แนวคิด Greedy เพื่อหากิจกรรมถัดไปที่มีเวลาสิ้นสุดน้อยที่สุดในกิจกรรมที่เหลือ และเวลาเริ่มต้นมากกว่าหรือเท่ากับเวลาสิ้นสุดของกิจกรรมที่เลือกล่าสุด

• ความซับซ้อนคือ O(n log n) เมื่อรายการยังไม่เรียงลำดับ หากมีรายการที่เรียงแล้ว จะเป็น O(n)

อินพุต

รายการกิจกรรมพร้อมเวลาเริ่มต้นและสิ้นสุด

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

เอาต์พุต

กิจกรรมที่เลือก:

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

อัลกอริทึม

maxActivity(act, size)

อินพุต - รายการกิจกรรมและจำนวนสมาชิก
เอาต์พุต - ลำดับกิจกรรมที่ถูกเลือก

เริ่มต้น
  เรียงลำดับรายการกิจกรรมที่กำหนด
  ตั้ง i := 1
  แสดงกิจกรรมที่ i (ในกรณีนี้คือกิจกรรมแรก)
  สำหรับ j := 1 ถึง n-1 ทำ
    ถ้าเวลาเริ่มต้นของ act[j] >= เวลาสิ้นสุดของ act[i] แล้ว
      แสดงกิจกรรมที่ j
      i := j
  จบลูป
สิ้นสุด

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

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

struct Activity {
    int start, end;
};

bool comp(Activity act1, Activity act2) {
    return (act1.end < act2.end);
}

void maxActivity(Activity act[], int n) {
    sort(act, act + n, comp); // เรียงกิจกรรมด้วยฟังก์ชันเปรียบเทียบ
    cout << "Selected Activities are: " << endl;
    int i = 0; // เลือกกิจกรรมแรกเป็น 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 actArr[] = {{5,9},{1,2},{3,4},{0,6},{5,7},{8,9}};
    int n = 6;
    maxActivity(actArr, n);
    return 0;
}

ผลลัพธ์

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