Lợi nhuận tối đa khi lên lịch công việc bằng C ++

Giả sử chúng ta có n nhiệm vụ khác nhau, trong đó mọi tác vụ được lên lịch thực hiện từ startTime [i] đến endTime [i], đối với nhiệm vụ đó, chúng ta sẽ nhận được lợi nhuận từ lợi nhuận [i]. Chúng tôi biết startTime, endTime và danh sách lợi nhuận, chúng tôi phải tìm lợi nhuận tối đa mà chúng tôi có thể thực hiện sao cho không có 2 nhiệm vụ nào trong tập hợp con có phạm vi thời gian trùng lặp. Nếu chúng ta chọn một nhiệm vụ kết thúc vào thời điểm X, chúng ta sẽ có thể bắt đầu một nhiệm vụ khác bắt đầu vào thời điểm X.

Vì vậy, nếu đầu vào là 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 vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một Dữ liệu với các giá trị đầu, cuối và giá trị
tạo một mảng Dữ liệu j
n:=kích thước của s
để khởi tạo i:=0, khi i
- Tạo một Nhiệt độ dữ liệu (s [i], e [i], p [i])
- chèn tạm thời vào cuối j
sắp xếp mảng j dựa trên thời gian kết thúc
Xác định một mảng dp có kích thước n
dp [0]:=j [0] .cost
để khởi tạo i:=1, khi i
- temp:=0, low:=0, high:=i - 1
- trong khi thấp
  - mid:=low + (high - low + 1) / 2
  - nếu j [mid] .end <=j [i] .start, thì -
    - thấp:=trung bình
  - Nếu không
    - cao:=mid - 1
  - dp [i]:=j [i] .cost
  - nếu j [low] .end <=j [i] .start, thì -
    - dp [i]:=dp [i] + dp [thấp]
- dp [i]:=tối đa là dp [i] và dp [i - 1]
trả về dp [n - 1]

Hãy cùng chúng tôi xem cách 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}

Lợi nhuận tối đa khi lên lịch công việc bằng C ++

Ví dụ

Đầu vào

Đầu ra