กำไรสูงสุดในการจัดตารางงานใน C++

สมมติว่ามี n งาน แต่ละงานมีเวลาเริ่มต้น startTime[i] เวลาสิ้นสุด endTime[i] และกำไร profit[i] ต้องหากำไรสูงสุดโดยไม่ให้งานทับซ้อนกันในเวลา (ถ้างานจบเวลา X สามารถเริ่มงานใหม่เวลา X ได้)

เช่น startTime=[1,2,3,3], endTime=[3,4,5,6], profit=[500,100,400,700] เอาต์พุต=1200

วิธีแก้ − เรียงงานตามเวลาสิ้นสุด ใช้ DP + Binary Search หางานก่อนหน้าที่ไม่ทับซ้อน

ตัวอย่าง

#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++) j.push_back(Data(s[i], e[i], p[i])); 
        sort(j.begin(), j.end(), cmp); 
        vector<int> dp(n); dp[0] = j[0].c; 
        for (int i = 1; i < n; i++) { 
            int low = 0, 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)); 
}

อินพุต

{1,2,3,3}, {3,4,5,6}, {500,100,400,700}

เอาต์พุต

1200