Formatted question description: https://leetcode.ca/all/826.html

826. Most Profit Assigning Work (Medium)

We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job.

Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i].

Every worker can be assigned at most one job, but one job can be completed multiple times.

For example, if 3 people attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, his profit is $0.

What is the most profit we can make?

Example 1:

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100 
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get profit of [20,20,30,30] seperately.

Notes:

1 <= difficulty.length = profit.length <= 10000
1 <= worker.length <= 10000
difficulty[i], profit[i], worker[i] are in range [1, 10^5]

Companies:
Nutanix

Related Topics:
Two Pointers

Solution 1.

class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int jobs = difficulty.length;
        int[][] difficultyProfit = new int[jobs][2];
        for (int i = 0; i < jobs; i++) {
            difficultyProfit[i][0] = difficulty[i];
            difficultyProfit[i][1] = profit[i];
        }
        Arrays.sort(difficultyProfit, new Comparator<int[]>() {
            public int compare(int[] difficultyProfit1, int[] difficultyProfit2) {
                if (difficultyProfit1[0] != difficultyProfit2[0])
                    return difficultyProfit1[0] - difficultyProfit2[0];
                else
                    return difficultyProfit2[1] - difficultyProfit1[1];
            }
        });
        for (int i = 1; i < jobs; i++)
            difficultyProfit[i][1] = Math.max(difficultyProfit[i - 1][1], difficultyProfit[i][1]);
        int totalProfit = 0;
        for (int ability : worker) {
            int maxProfit = binarySearch(difficultyProfit, ability);
            totalProfit += maxProfit;
        }
        return totalProfit;
    }

    public int binarySearch(int[][] difficultyProfit, int ability) {
        int low = 0, high = difficultyProfit.length - 1;
        int index = -1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int difficulty = difficultyProfit[mid][0];
            if (difficulty == ability) {
                index = mid;
                break;
            } else if (difficulty > ability)
                high = mid - 1;
            else
                low = mid + 1;
        }
        if (index < 0)
            index = low - 1;
        if (index < 0)
            return 0;
        else
            return difficultyProfit[index][1];
    }
}

############

class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int n = difficulty.length;
        List<int[]> job = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            job.add(new int[] {difficulty[i], profit[i]});
        }
        job.sort(Comparator.comparing(a -> a[0]));
        Arrays.sort(worker);
        int res = 0;
        int i = 0, t = 0;
        for (int w : worker) {
            while (i < n && job.get(i)[0] <= w) {
                t = Math.max(t, job.get(i++)[1]);
            }
            res += t;
        }
        return res;
    }
}

// OJ: https://leetcode.com/problems/most-profit-assigning-work/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        map<int, int, greater<int>> diffToProfit;
        int N = difficulty.size(), maxProfit = 0, ans = 0;
        for (int i = 0; i < N; ++i) {
            diffToProfit[difficulty[i]] = max(diffToProfit[difficulty[i]], profit[i]);
        }
        for (auto it = diffToProfit.rbegin(); it != diffToProfit.rend(); ++it) {
            it->second = maxProfit = max(maxProfit, it->second);
        }
        for (int w : worker) {
            auto it = diffToProfit.lower_bound(w);
            if (it != diffToProfit.end()) ans += it->second;
        }
        return ans;
    }
};

class Solution:
    def maxProfitAssignment(
        self, difficulty: List[int], profit: List[int], worker: List[int]
    ) -> int:
        n = len(difficulty)
        job = [(difficulty[i], profit[i]) for i in range(n)]
        job.sort(key=lambda x: x[0])
        worker.sort()
        i = t = res = 0
        for w in worker:
            while i < n and job[i][0] <= w:
                t = max(t, job[i][1])
                i += 1
            res += t
        return res

############

class Solution(object):
    def maxProfitAssignment(self, difficulty, profit, worker):
        """
        :type difficulty: List[int]
        :type profit: List[int]
        :type worker: List[int]
        :rtype: int
        """
        jobs = sorted([a, b] for a, b in zip(difficulty, profit))
        curMax, i = 0, 0
        res = 0
        for w in sorted(worker):
            while i < len(jobs) and w >= jobs[i][0]:
                curMax = max(curMax, jobs[i][1])
                i += 1
            res += curMax
        return res

func maxProfitAssignment(difficulty []int, profit []int, worker []int) int {
	var job [][2]int
	for i := range difficulty {
		job = append(job, [2]int{difficulty[i], profit[i]})
	}

	sort.SliceStable(job, func(i, j int) bool { return job[i][0] <= job[j][0] })
	sort.Ints(worker)
	i, t, n, res := 0, 0, len(difficulty), 0
	for _, w := range worker {
		for i < n && job[i][0] <= w {
			t = max(t, job[i][1])
			i++
		}
		res += t
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

826 - Most Profit Assigning Work

826. Most Profit Assigning Work (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

826. Most Profit Assigning Work (Medium)

Solution 1.

All Problems

All Solutions