मान लीजिए हमारे पास जॉब्स की कठिनाई difficulty[i] है और यह सरणी i-वें जॉब की कठिनाई दर्शाती है, और profit[i] i-वें जॉब का लाभ है। अब मान लीजिए हमारे पास कुछ श्रमिक हैं। worker[i] i-वें श्रमिक की क्षमता है, इसका मतलब है कि यह श्रमिक केवल अधिकतम worker[i] कठिनाई वाला जॉब पूरा कर सकता है। प्रत्येक श्रमिक अधिकतम एक जॉब कर सकता है, लेकिन एक जॉब को कई बार पूरा किया जा सकता है। हमें ढूंढना है कि हम अधिकतम कितना लाभ कमा सकते हैं?
उदाहरण के लिए, यदि इनपुट difficulty = [2,4,6,8,10] और profit = [10,20,30,40,50] और worker = [4,5,6,7] है, तो आउटपुट 100 होगा। श्रमिकों को जॉब कठिनाई [4,4,6,6] असाइन की जा सकती है, और प्राप्त लाभ [20,20,30,30], जो कुल 100 है।
हल करने के चरण
- ans := 0 और n := profit सरणी का आकार
- worker सरणी को सॉर्ट करें
- पेयर्स की एक सूची v बनाएं
- i को 0 से n-1 तक लूप करें
- पेयर (difficulty[i], profit[i]) को v में डालें
- v सरणी को सॉर्ट करें
- maxVal := 0, m := worker सरणी का आकार और j := 0
- i को 0 से m-1 तक लूप करें
- जब तक j < n और v[j] का पहला मान <= worker[i]
- maxVal := max(maxVal, v[j] का दूसरा मान)
- j को 1 से बढ़ाएं
- ans := ans + maxVal
- जब तक j < n और v[j] का पहला मान <= worker[i]
- ans वापस करें
उदाहरण
#include <bits/stdc++.h> using namespace std; class Solution { public: int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) { int ans = 0; sort(worker.begin(), worker.end()); vector < pair <int, int> > v; int n = profit.size(); // जॉब्स की संख्या for(int i = 0; i < n; i++){ v.push_back({difficulty[i], profit[i]}); } sort(v.begin(), v.end()); int maxVal = 0; int m = worker.size(); // श्रमिकों की संख्या int j = 0; for(int i = 0; i < m; i++){ while(j < n && v[j].first <= worker[i]){ maxVal = max(maxVal, v[j].second); j++; } ans += maxVal; } return ans; } }; int main() { Solution ob1; vector<int> difficulty{2,4,6,8,10}; vector<int> profit{10,20,30,40,50}; vector<int> worker{4,5,6,7}; cout << ob1.maxProfitAssignment(difficulty, profit, worker) << endl; return 0; }इनपुट
[2,4,6,8,10] [10,20,30,40,50] [4,5,6,7]
आउटपुट
100