C++ में जॉब शेड्यूल की न्यूनतम कठिनाई

मान लीजिए कि हम d दिनों में कार्यों की एक सूची शेड्यूल करना चाहते हैं। कार्य निर्भर हैं इसलिए i-th कार्य पर काम करने के लिए, हमें सभी कार्यों को पूरा करना होगा जहां 0 <=j

हमें प्रत्येक दिन में कम से कम एक कार्य पूरा करना होता है। कार्य अनुसूची की कठिनाई वास्तव में दिनों की संख्या के प्रत्येक दिन की कठिनाइयों का योग है। एक दिन की कठिनाई उस दिन किए गए कार्य की अधिकतम कठिनाई होती है।

इसलिए हमारे पास पूर्णांकों की एक सरणी है जिसे कार्य कठिनाई और एक पूर्णांक d कहा जाता है। I-th जॉब की कठिनाई है taskDifficulty[i]। हमें एक कार्य अनुसूची की न्यूनतम कठिनाई का पता लगाना है। यदि हमें कार्यों के लिए शेड्यूल नहीं मिल रहा है, तो -1 पर लौटें।

इसलिए, यदि इनपुट कार्य कठिनाई =[6,5,4,3,2,1], d =2,

तो आउटपुट 7 होगा, क्योंकि पहले दिन हम पहले 5 काम खत्म कर सकते हैं, कुल कठिनाई 6 है। अब दूसरे दिन हम आखिरी काम खत्म कर सकते हैं, कुल कठिनाई 1 है, इसलिए शेड्यूल की कठिनाई होगी 6 + 1 =7.

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

• एक फ़ंक्शन हल करें () को परिभाषित करें, यह एक सरणी v, idx, k, एक 2D dp,

  लेगा

• यदि idx, v के आकार के समान है और k, 0 के समान है, तो -

  • वापसी 0

• यदि k <0 या idx, v और k> 0 के आकार के समान है, तो -

  • वापसी 1^6

• अगर dp[idx, k] -1 के बराबर नहीं है, तो -

  • वापसी डीपी [आईडीएक्स, के]

• मैक्सवैल :=0

• रिट :=inf

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

  • maxVal :=अधिकतम v[i] और maxVal

  • रिट :=न्यूनतम रिट और मैक्सवैल + सॉल्व(v, i + 1, k-1, dp)

• dp[idx, k] :=ret

• वापसी रिट

• मुख्य विधि से निम्न कार्य करें -

• n :=j का आकार

• यदि d> n, तो -

  • वापसी -1

• आकार n x (d + 1) के एक 2D सरणी dp को परिभाषित करें और इसे -1 से भरें

• वापसी हल (जे, 0, डी, डीपी)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& v, int idx, int k, vector<vector<int> >&
   dp){
      if (idx == v.size() && k == 0)
      return 0;
      if (k < 0 || idx == v.size() && k > 0)
      return 1e6;
      if (dp[idx][k] != -1)
      return dp[idx][k];
      int maxVal = 0;
      int ret = INT_MAX;
      for (int i = idx; i < v.size(); i++) {
         maxVal = max(v[i], maxVal);
         ret = min(ret, maxVal + solve(v, i + 1, k - 1, dp));
      }
      return dp[idx][k] = ret;
   }
   int minDifficulty(vector<int>& j, int d){
      int n = j.size();
      if (d > n)
      return -1;
      vector<vector<int> > dp(n, vector<int>(d + 1, -1));
      return solve(j, 0, d, dp);
   }
};
main(){
   Solution ob;
   vector<int> v = {6,5,4,3,2,1};
   cout << (ob.minDifficulty(v, 2));
}

इनपुट

{6,5,4,3,2,1}, 2

आउटपुट

7