สมมติว่าเรามีรายการ N งาน โดยแต่ละงานมี 3 พารามิเตอร์ 1. Start Time 2. Finish Time 3. Profit เราต้องหาส่วนย่อยของงานที่เกี่ยวข้องกับ maximum profit เพื่อที่จะไม่มีงานสองงานในส่วนย่อยที่ overlap กัน
ดังนั้น ถ้า input เป็นแบบ N = 4 และ J = {{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}} แล้ว output จะเป็น [(2, 3, 55),(3, 150, 250)] และ optimal profit 305
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ −
กำหนดฟังก์ชัน find_no_conflict() ซึ่งจะรับ array jobs, index
left := 0, right := index - 1
while left <= right ให้ทำ −
mid := (left + right) / 2
ถ้า jobs[mid].finish <= jobs[index].start แล้ว −
ถ้า jobs[mid + 1].finish <= jobs[index].start แล้ว −
left := mid + 1
คืนค่า mid
คืนค่า mid
มิฉะนั้น
right := mid - 1
คืนค่า -1
จาก main method ให้ทำดังนี้ −
เรียงอาร์เรย์ job_list ตาม finish time
สร้างตารางสำหรับ jobs ชื่อ table ขนาด n
table[0].value := job_list[0].profit
insert job_list[0] ไปที่ท้ายของ table[0]
for เริ่ม i := 1 เมื่อ i < n อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ −
include_profit := job_list[i].profit
l := find_no_conflict(job_list, i)
ถ้า l ไม่เท่ากับ -1 แล้ว −
include_profit := include_profit + table[l].value
ถ้า include_profit > table[i - 1].value แล้ว −
table[i].value := include_profit
table[i].job := table[l].job
insert job_list[i] ไปที่ท้ายของ table[i]
มิฉะนั้น
table[i] := table[i - 1]
แสดงงานจาก table
แสดง Optimal profit := table[n - 1].value
ตัวอย่าง (C++)
ลองดูการนำไปใช้ต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น −
#include <bits/stdc++.h> using namespace std; class Job { public: int start, finish, profit; }; struct job_with_weight { vector<Job> job; int value; }; bool jobComparator(Job s1, Job s2) { return (s1.finish < s2.finish); } int find_no_conflict(Job jobs[], int index) { int left = 0, right = index - 1; while (left <= right) { int mid = (left + right) / 2; if (jobs[mid].finish <= jobs[index].start) { if (jobs[mid + 1].finish <= jobs[index].start) left = mid + 1; else return mid; } else right = mid - 1; } return -1; } int get_max_profit(Job job_list[], int n) { sort(job_list, job_list + n, jobComparator); job_with_weight table[n]; table[0].value = job_list[0].profit; table[0].job.push_back(job_list[0]); for (int i = 1; i < n; i++) { int include_profit = job_list[i].profit; int l = find_no_conflict(job_list, i); if (l != - 1) include_profit += table[l].value; if (include_profit > table[i - 1].value){ table[i].value = include_profit; table[i].job = table[l].job; table[i].job.push_back(job_list[i]); } else table[i] = table[i - 1]; } cout << "["; for (int i=0; i<table[n-1].job.size(); i++) { Job j = table[n-1].job[i]; cout << "(" << j.start << ", " << j.finish << ", " << j.profit << "),"; } cout << "]\nOptimal profit: " << table[n - 1].value; } int main() { Job arr[] = {{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}}; int n = sizeof(arr)/sizeof(arr[0]); get_max_profit(arr, n); }อินพุต
{{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}}เอาต์พุต
[(2, 3, 55),(3, 150, 250),] Optimal profit: 305
