Bài toán Job Sequencing with Deadlines (Lập lịch công việc có deadline)

Cho danh sách các công việc, mỗi công việc có deadline (hạn chót) và profit (lợi nhuận). Mỗi công việc mất 1 đơn vị thời gian, deadline tối thiểu là 1. Chỉ chạy được 1 job tại một thời điểm. Mục tiêu: tối đa hóa tổng profit.

Giải: Sinh tất cả subset của tập job để kiểm tra tính khả thi, theo dõi profit lớn nhất.

Độ phức tạp: O(n²)

Input và Output

Input: Danh sách job (id, deadline, profit):
{('a', 2, 100), ('b', 1, 19), ('c', 2, 27), ('d', 1, 25), ('e', 3, 15)}
n = 5
Output: Chuỗi job lợi nhuận tối đa: c a e

Thuật toán

jobSequence(jobList, n)
Input: Danh sách job, số lượng job
Output: Thứ tự job được chọn

Begin
  sắp xếp jobList theo profit giảm dần
  tạo mảng jobSeq và slot theo dõi time slot trống
  ban đầu tất cả slot đều trống
  for tất cả job i do
    for j từ min(n, jobList[i].deadline)-1 xuống 0 do
      if slot[j] trống then
        jobSeq[j] := i
        slot[j] := filled
        break
      done
    done
  done
  for tất cả slot không trống do
    in id của job dùng jobList[jobSeq[i]]
  done
End

Ví dụ (C++)

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

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

bool comp(Job j1, Job j2) { return j1.profit > j2.profit; }

int min(int a, int b) { return (a < b) ? a : b; }

void jobSequence(Job jobList[], int n) {
    sort(jobList, jobList + n, comp);
    int jobSeq[n];
    bool slot[n];
    for(int i = 0; i < n; i++) slot[i] = false;
    for(int i = 0; i < n; i++) {
        for(int j = min(n, jobList[i].deadLine) - 1; j >= 0; j--) {
            if(slot[j] == false) {
                jobSeq[j] = i;
                slot[j] = true;
                break;
            }
        }
    }
    for(int i = 0; i < n; i++)
        if(slot[i]) cout << jobList[jobSeq[i]].id << " ";
}

int main() {
    Job jobList[] = {{'a',2,100}, {'b',1,19}, {'c',2,27}, {'d',1,25}, {'e',3,15}};
    int n = 5;
    cout << "Chuỗi job lợi nhuận tối đa: ";
    jobSequence(jobList, n);
}

Kết quả

Chuỗi job lợi nhuận tối đa: c a e

Giải thích: Sắp xếp theo profit giảm: a(100), c(27), d(25), b(19), e(15). Chèn a vào slot 1 (deadline 2), c vào slot 0 (deadline 2), d/b không chèn được (slot 0,1 đầy), e vào slot 2 (deadline 3). Kết quả: c(0), a(1), e(2).