C++ में जॉब शेड्यूलिंग में अधिकतम लाभ

मान लीजिए कि हमारे पास अलग-अलग कार्य हैं, जहां प्रत्येक कार्य प्रारंभ समय [i] से समाप्ति समय [i] तक किया जाना निर्धारित है, उस कार्य के लिए हमें लाभ का लाभ मिलता है [i]। हम स्टार्टटाइम, एंडटाइम और प्रॉफिट लिस्ट को जानते हैं, हमें अधिकतम लाभ का पता लगाना होगा जो हम इस तरह ले सकते हैं कि ओवरलैपिंग टाइम रेंज के साथ सबसेट में 2 कार्य न हों। यदि हम समय X पर समाप्त होने वाले कार्य को चुनते हैं तो हम समय X पर शुरू होने वाले अन्य कार्य को प्रारंभ करने में सक्षम होंगे।

इसलिए, यदि इनपुट स्टार्टटाइम =[1,2,3,3], एंडटाइम =[3,4,5,6] लाभ =[500,100,400,700]

तो आउटपुट 1200

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक डेटा को प्रारंभ, समाप्ति और लागत मानों के साथ परिभाषित करें

• डेटा j की एक सरणी बनाएं

• n :=s का आकार

• इनिशियलाइज़ i :=0 के लिए, जब i

  • एक डेटा अस्थायी बनाएं (s[i], e[i], p[i])

  • j के अंत में अस्थायी डालें

• अंत समय के आधार पर सरणी j को क्रमबद्ध करें

• n आकार की dp सरणी परिभाषित करें

• डीपी [0] :=j[0].लागत

• इनिशियलाइज़ i :=1 के लिए, जब i

  • अस्थायी:=0, निम्न:=0, उच्च:=i - 1

  • जबकि कम <उच्च, करें -

    • मध्य :=निम्न + (उच्च - निम्न + 1) / 2

    • अगर j[mid].end <=j[i].start, तो -

      • कम :=मध्य

    • अन्यथा

      • उच्च :=मध्य - 1

    • डीपी [i] :=j[i].लागत

    • अगर j[low].end <=j[i].start, तो -

      • डीपी [i]:=डीपी [i] + डीपी [कम]

  • dp[i] :=अधिकतम dp[i] और dp[i - 1]

• वापसी डीपी [एन -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