Job Sequencing Problem with Deadlines (ปัญหาลำดับงานมีกำหนดส่ง)

Job Sequencing with Deadlines เป็นปัญหาเพื่อเพิ่มกำไรสูงสุด โดยมีงานหลายงาน แต่ละงานมี กำหนดส่ง (Deadline) และ กำไร (Profit) งานแต่ละงานใช้เวลา 1 หน่วย สามารถทำได้งานเดียวในเวลาเดียวกัน

ตัวอย่างปัญหา

Jobs: {('a', 2, 100), ('b', 1, 19), ('c', 2, 27), ('d', 1, 25), ('e', 3, 15)}
Format: (JobID, Deadline, Profit)
n = 5

Output: c a e  (กำไรรวม = 27 + 100 + 15 = 142)

แนวคิดการทำงาน (Greedy Approach)

1. จัดเรียงงานตาม กำไรจากมากไปน้อย
2. สร้างช่องเวลา (Slots) ตาม deadline สูงสุด
3. สำหรับแต่ละงาน (ตามลำดับกำไร): วางใน ช่องเวลาสุดท้ายที่ว่าง ก่อน deadline
4. ถ้าไม่มีช่องว่าง ข้ามงานนั้นไป

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

jobSequence(jobList, n)
  sort jobList by profit descending
  create slot[0..n-1] = false  // free slots
  create jobSeq[0..n-1]

  for i = 0 to n-1:
    for j = min(n, jobList[i].deadline) - 1 down to 0:
      if slot[j] == false:
        jobSeq[j] = i
        slot[j] = true
        break

  for i = 0 to n-1:
    if slot[i] == true:
      print jobList[jobSeq[i]].id

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

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

struct Job {
    char id;
    int deadline;
    int profit;
};

bool compare(Job a, Job b) {
    return a.profit > b.profit;
}

void jobSequence(Job jobList[], int n) {
    sort(jobList, jobList + n, compare);

    int jobSeq[n];
    bool slot[n] = {false};

    for (int i = 0; i < n; i++) {
        for (int j = min(n, jobList[i].deadline) - 1; j >= 0; j--) {
            if (!slot[j]) {
                jobSeq[j] = i;
                slot[j] = true;
                break;
            }
        }
    }

    cout << "Sequence: ";
    for (int i = 0; i < n; i++)
        if (slot[i]) cout << jobList[jobSeq[i]].id << " ";
    cout << endl;
}

int main() {
    Job jobs[] = {{'a',2,100}, {'b',1,19}, {'c',2,27}, {'d',1,25}, {'e',3,15}};
    int n = 5;
    jobSequence(jobs, n);
}

คุณสมบัติ

• Time Complexity: O(n²) - เนื่องจาก nested loop
• Space Complexity: O(n)
• Greedy Choice: เลือกงานกำไรสูงสุดก่อน วางในช่องสุดท้ายที่ทำได้
• Optimal: ให้คำตอบที่เหมาะสมที่สุดเสมอ

การปรับปรุงประสิทธิภาพ

ใช้ Disjoint Set Union (DSU / Union-Find) หาช่องว่างได้ใน O(α(n)) ทำให้รวมเป็น O(n log n)