php 解法, 执行用时: 112 ms, 内存消耗: 23 MB, 提交时间: 2024-05-17 09:27:06

class Solution {

    /**
     * @param Integer[] $difficulty
     * @param Integer[] $profit
     * @param Integer[] $worker
     * @return Integer
     */
    function maxProfitAssignment1($difficulty, $profit, $worker) {
        $length = count($difficulty);
        $sum = 0;
        foreach ($worker as $w) {
            $result = 0;
            for ($i=0; $i < $length; $i++) {
                if($w >= $difficulty[$i] && $result < $profit[$i]) {
                    $result = $profit[$i];
                }
            }
            $sum += $result;
        }
        return $sum;
    }

    // 2
    function maxProfitAssignment($difficulty, $profit, $worker) {
        $temp = [];
        for ($i=0; $i < count($difficulty); $i++) { 
            $temp[$difficulty[$i]] = $temp[$difficulty[$i]] ? max($temp[$difficulty[$i]],$profit[$i]): $profit[$i];
        }
        sort($difficulty);
        sort($worker);
        $length = count($difficulty);
        $sum = 0;
        $lastIdx= 0;
        $preMax= 0;
        foreach ($worker as $w) {
            while ($w >= $difficulty[$lastIdx] && $lastIdx < $length) {
                $preMax = max($preMax,$temp[$difficulty[$lastIdx]]);
                $lastIdx++;
            }
            $sum += $preMax;
        }
        return $sum;
    }
}

java 解法, 执行用时: 16 ms, 内存消耗: 44.4 MB, 提交时间: 2024-05-17 09:13:22

class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int n = difficulty.length;
        int[][] jobs = new int[n][2];
        for (int i = 0; i < n; i++) {
            jobs[i][0] = difficulty[i];
            jobs[i][1] = profit[i];
        }
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
        Arrays.sort(worker);
        int ans = 0, j = 0, maxProfit = 0;
        for (int w : worker) {
            while (j < n && jobs[j][0] <= w) {
                maxProfit = Math.max(maxProfit, jobs[j++][1]);
            }
            ans += maxProfit;
        }
        return ans;
    }
}

javascript 解法, 执行用时: 118 ms, 内存消耗: 59 MB, 提交时间: 2024-05-17 09:12:58

/**
 * @param {number[]} difficulty
 * @param {number[]} profit
 * @param {number[]} worker
 * @return {number}
 */
var maxProfitAssignment = function(difficulty, profit, worker) {
    const jobs = _.zip(difficulty, profit).sort((a, b) => a[0] - b[0]);
    worker.sort((a, b) => a - b);
    let ans = 0, j = 0, maxProfit = 0;
    for (const w of worker) {
        while (j < jobs.length && jobs[j][0] <= w) {
            maxProfit = Math.max(maxProfit, jobs[j++][1]);
        }
        ans += maxProfit;
    }
    return ans;
};

rust 解法, 执行用时: 8 ms, 内存消耗: 2.5 MB, 提交时间: 2023-09-25 15:15:35

impl Solution {
    pub fn max_profit_assignment(difficulty: Vec<i32>, profit: Vec<i32>, mut worker: Vec<i32>) -> i32 {
        let mut jobs = difficulty.iter().zip(profit.iter()).collect::<Vec<_>>();
        jobs.sort_unstable();
        worker.sort_unstable();
        let (mut ans, mut cur) = (0, 0);
        let mut i = 0;
        for skill in worker {
            while i < jobs.len() && skill >= *jobs[i].0 {
                cur = cur.max(*jobs[i].1);
                i += 1;
            }
            ans += cur;
        }
        ans
    }
}

golang 解法, 执行用时: 56 ms, 内存消耗: 6.7 MB, 提交时间: 2023-09-25 15:14:53

type pair struct {
	d, p int
}

func maxProfitAssignment(difficulty []int, profit []int, worker []int) int {
	jobs := make([]pair, len(difficulty))
	for i := range jobs {
		jobs[i].d = difficulty[i]
		jobs[i].p = profit[i]
	}
	sort.Slice(jobs, func(i, j int) bool {
		return jobs[i].d < jobs[j].d
	})
	sort.Ints(worker)
	var j, best, res int
	for i := range worker {
		for j < len(jobs) && worker[i] >= jobs[j].d {
			best = max(best, jobs[j].p)
			j++
		}
		res += best
	}
	return res
}
func max(a, b int) int { if a > b { return a }; return b }

python3 解法, 执行用时: 124 ms, 内存消耗: 18.8 MB, 提交时间: 2023-09-25 15:13:44

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = list(zip(difficulty, profit))
        jobs.sort()
        ans = i = best = 0
        for skill in sorted(worker):
            while i < len(jobs) and skill >= jobs[i][0]:
                best = max(best, jobs[i][1])
                i += 1
            ans += best
        return ans

java 解法, 执行用时: 15 ms, 内存消耗: 43.9 MB, 提交时间: 2023-09-25 15:12:26

import java.awt.Point;

class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int N = difficulty.length;
        Point[] jobs = new Point[N];
        for (int i = 0; i < N; ++i)
            jobs[i] = new Point(difficulty[i], profit[i]);
        Arrays.sort(jobs, (a, b) -> a.x - b.x); // 工作按难度排序
        Arrays.sort(worker);  // 工人按能力排序

        int ans = 0, i = 0, best = 0;
        for (int skill: worker) {
            while (i < N && skill >= jobs[i].x)
                best = Math.max(best, jobs[i++].y);
            ans += best;
        }

        return ans;
    }
}