জবের ডিফিকাল্টি difficulty[i] এবং প্রফিট profit[i]। ওয়ার্কারের অভিযোগিতা worker[i] = সে difficulty <= worker[i] वाला জব করতে পারে। প্রতিটি ওয়ার্কার একটা জব, এক জব একাধিকবার করা যায়। সর্বোচ্চ প্রফিট বের করতে হবে।
উদাহরণ: difficulty=[2,4,6,8,10], profit=[10,20,30,40,50], worker=[4,5,6,7] → ১০০।
সমাধানের ধাপসমূহ
- ওয়ার্কার অ্যারে সাজান।
- জবগুলো (ডিফিকাল্টি, প্রফিট) পেয়ার বানিয়ে ডিফিকাল্টি অনুযায়ী সাজান।
- টু-পয়েন্টার: ওয়ার্কার লুপে, যত জবের ডিফিকাল্টি <= ওয়ার্কারের অভিযোগিতা, সেগুলোর ম্যাক্স প্রফিট ট্র্যাক করুন।
- প্রতিটি ওয়ার্কারের জন্য সেই ম্যাক্স প্রফিট যোগ করুন।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
sort(worker.begin(), worker.end());
vector<pair<int, int>> jobs;
for (int i = 0; i < profit.size(); i++)
jobs.push_back({difficulty[i], profit[i]});
sort(jobs.begin(), jobs.end());
int ans = 0, maxVal = 0, j = 0;
for (int w : worker) {
while (j < jobs.size() && jobs[j].first <= w) {
maxVal = max(maxVal, jobs[j].second);
j++;
}
ans += maxVal;
}
return ans;
}
};
int main() {
vector<int> diff = {2,4,6,8,10};
vector<int> prof = {10,20,30,40,50};
vector<int> work = {4,5,6,7};
Solution ob;
cout << ob.maxProfitAssignment(diff, prof, work);
}
ইনপুট
[2,4,6,8,10] [10,20,30,40,50] [4,5,6,7]
আউটপুট
100
