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

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

ดังนั้น หากอินพุตเป็นเหมือน startTime =[1,2,3,3] endTime =[3,4,5,6] profit =[500,100,400,700]

แล้วผลลัพธ์จะเป็น 1200

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดข้อมูลหนึ่งรายการด้วยค่าเริ่มต้น สิ้นสุด และต้นทุน

• สร้างอาร์เรย์ของข้อมูล j

• n :=ขนาดของ s

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • สร้างหนึ่ง Data temp(s[i], e[i], p[i])

  • ใส่ temp ที่ท้าย j

• จัดเรียงอาร์เรย์ j ตามเวลาสิ้นสุด

• กำหนดขนาดอาร์เรย์ dp n

• dp[0] :=j[0].cost

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน

  • อุณหภูมิ :=0, ต่ำ :=0, สูง :=i - 1

  • ในขณะที่ต่ำ <สูง ทำ -

    • กลาง :=ต่ำ + (สูง - ต่ำ + 1) / 2

    • ถ้า j[mid].end <=j[i].start แล้ว −

      • ต่ำ :=กลาง

    • มิฉะนั้น

      • สูง :=กลาง - 1

    • dp[i] :=j[i].cost

    • ถ้า j[low].end <=j[i].start แล้ว −

      • dp[i] :=dp[i] + dp[ต่ำ]

  • dp[i] :=สูงสุดของ dp[i] และ dp[i - 1]

• กลับ dp[n - 1]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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));
}

อินพุต

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

ผลลัพธ์

1200