[LeetCode]Most Profit Assigning Work

这道题相同的task允许取多次，所以本质上就是对于一个worker来说，我们要找difficulty在[0, x]之间的最大profit，x为小于等于worker能承受范围的最大值。那么我们可以维护一个sorted的序列，按照task的difficulty从小到大排序，break tie by profit从小到大。那么对于每一个task 的difficulty di，我们用一个array a[]存小于等于di的task中的最大profit a[i]，我们从左到右扫一次就可以构建好a。之后对于每一个worker，我们在a中binary search找到difficulty小于worker[i]的最大值对应的值，这就是worker[i]所能达到的最大profit。我们对每一个worker都重复这个操作即可。假设有n个task，m个worker，时间复杂度为O(n * log n + m * log n)，空间复杂度O(n)。代码如下：

	class Solution {
	public:
	int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
	int n = difficulty.size(), m = worker.size();
	vector<int> idxes(n);
	for (int i = 0; i < n; ++i)idxes[i] = i;
	auto comp = [&](const int lhs, const int rhs) {return difficulty[lhs] == difficulty[rhs] ? profit[lhs] < profit[rhs] : difficulty[lhs] < difficulty[rhs]; };
	sort(idxes.begin(), idxes.end(), comp);
	for(int i = 1; i < n; ++i)profit[idxes[i]] = max(profit[idxes[i - 1]], profit[idxes[i]]);
	int res = 0;
	for(int i = 0; i < m; ++i)
	{
	int idx = binarySearch(idxes, difficulty, worker[i]);
	if(idx == -1)continue;
	res += profit[idxes[idx]];
	}
	return res;
	}
	private:
	int binarySearch(vector<int>& idxes, vector<int>& difficulty, int worker)
	{
	int lo = 0, n = idxes.size(), hi = n - 1;
	while(lo <= hi)
	{
	int mid = lo + (hi - lo) / 2, idx = idxes[mid];
	if(difficulty[idx] <= worker)lo = mid + 1;
	else hi = mid - 1;
	}
	return hi;
	}
	};

view raw Most Profit Assigning Work_bs.cpp hosted with ❤ by GitHub

另一种放方法，如果worker的array是sorted的话，我们要在a中找的对应的元素也是单调递增的，所以双指针就完全可以解决这个问题。同时因为我们是从左向右扫的，只需要用一个变量维护遇到过的最大profit就可以了，也就是说a数组我们也不需要了。时间复杂度O(m + n + m * log m + n * log n)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
	int n = difficulty.size(), m = worker.size();
	vector<int> idxes(n);
	for (int i = 0; i < n; ++i)idxes[i] = i;
	auto comp = [&](const int lhs, const int rhs) {return difficulty[lhs] == difficulty[rhs] ? profit[lhs] < profit[rhs] : difficulty[lhs] < difficulty[rhs]; };
	sort(idxes.begin(), idxes.end(), comp);
	sort(worker.begin(), worker.end());
	int i = 0, j = 0, maxProfit = 0, res = 0;
	while (i < n || j < m)
	{
	if(j == m)break;
	if(i == n){res += maxProfit * (m - j); break;}
	int idx = idxes[i];
	if(difficulty[idx] > worker[j]){res += maxProfit; ++j;}
	else{maxProfit = max(maxProfit, profit[idx]); ++i;}
	}
	return res;
	}
	};

view raw Most Profit Assigning Work.cpp hosted with ❤ by GitHub