Giả sử chúng ta có n công việc khác nhau, nơi mỗi công việc được lên lịch thực hiện từ startTime[i] đến endTime[i], cho công việc đó chúng ta cũng nhận được lợi nhuận profit[i]. Biết danh sách startTime, endTime và profit, chúng ta phải tìm lợi nhuận tối đa có thể đạt được sao cho không có 2 công việc trong tập con nào có khoảng thời gian chồng chéo. Nếu chúng ta chọn một công việc kết thúc tại thời điểm X, chúng ta sẽ có thể bắt đầu công việc khác bắt đầu tại thời điểm X.
Vì vậy, nếu đầu vào giống như startTime = [1,2,3,3], endTime = [3,4,5,6] profit = [500,100,400,700]
thì đầu ra sẽ là 1200
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
- Định nghĩa một cấu trúc Data với start, end và cost
tạo mảng Data j
n := kích thước của s
for khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), thực hiện −
Tạo một Data temp(s[i], e[i], p[i])
chèn temp vào cuối j
sắp xếp mảng j dựa trên thời gian kết thúc
Định nghĩa mảng dp kích thước n
dp[0] := j[0].cost
for khởi tạo i := 1, khi i < n, cập nhật (tăng i lên 1), thực hiện −
temp := 0, low := 0, high := i - 1
khi low < high, thực hiện −
mid := low + (high - low + 1) / 2
nếu j[mid].end <= j[i].start, thì −
low := mid
Ngược lại
high := mid - 1
dp[i] := j[i].cost
nếu j[low].end <= j[i].start, thì −
dp[i] := dp[i] + dp[low]
dp[i] := max của dp[i] và dp[i - 1]
trả về dp[n - 1]
Hãy xem triển khai sau để hiểu rõ hơn −
Ví dụ
#include <bits/stdc++.h> using namespace std; struct Data{ int s,e,c; Data(int x, int y, int z){ s= x; e= y; c = z; } }; bool cmp(Data a, Data b){ return a.e<b.e; } class Solution { public: int jobScheduling(vector<int>& s, vector<int>& e, vector<int>& p){ vector<Data> j; int n = s.size(); for (int i = 0; i < n; i++) { Data temp(s[i], e[i], p[i]); j.push_back(temp); } sort(j.begin(), j.end(), cmp); vector<int> dp(n); dp[0] = j[0].c; for (int i = 1; i < n; i++) { int temp = 0; int low = 0; int high = i - 1; while (low < high) { int mid = low + (high - low + 1) / 2; if (j[mid].e <= j[i].s) low = mid; else high = mid - 1; } dp[i] = j[i].c; if (j[low].e <= j[i].s) dp[i] += dp[low]; dp[i] = max(dp[i], dp[i - 1]); } return dp[n - 1]; } }; main(){ Solution ob; vector<int> startTime = {1,2,3,3}, endTime = {3,4,5,6}, profit = {500,100,400,700}; cout << (ob.jobScheduling(startTime, endTime, profit)); } Đầu vào
{1,2,3,3}, {3,4,5,6}, {500,100,400,700} Đầu ra
1200