826. Most Profit Assigning Work #

题目 #

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.

Note:

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

题目大意 #

这道题考察的是滑动窗口的问题，也是排序相关的问题。

给出一组任务，每个任务都有一定的难度，每个任务也都有完成以后对应的收益(完成难的任务不一定收益最高)。有一批工人，每个人能处理的任务难度不同。要求输出这批工人完成任务以后的最大收益。

解题思路 #

先将任务按照难度排序，工人也按照能处理任务难度的能力排序。用一个数组记录下，每个 i 下标，当前能达到的最大收益。计算这个收益只需要从下标为 1 开始，依次比较自己和前一个的收益即可(因为排过序，难度是依次递增的)。有了这个难度依次递增，并且记录了最大收益的数组以后，就可以计算最终结果了。遍历一遍工人数组，如果工人的能力大于任务的难度，就加上这个最大收益。遍历完工人数组，最终结果就是最大收益。

代码 #

package leetcode

import (
	"fmt"
	"sort"
)

// Task define
type Task struct {
	Difficulty int
	Profit     int
}

// Tasks define
type Tasks []Task

// Len define
func (p Tasks) Len() int { return len(p) }

// Swap define
func (p Tasks) Swap(i, j int) { p[i], p[j] = p[j], p[i] }

// SortByDiff define
type SortByDiff struct{ Tasks }

// Less define
func (p SortByDiff) Less(i, j int) bool {
	return p.Tasks[i].Difficulty < p.Tasks[j].Difficulty
}

func maxProfitAssignment(difficulty []int, profit []int, worker []int) int {
	if len(difficulty) == 0 || len(profit) == 0 || len(worker) == 0 {
		return 0
	}
	tasks, res, index := []Task{}, 0, 0
	for i := 0; i < len(difficulty); i++ {
		tasks = append(tasks, Task{Difficulty: difficulty[i], Profit: profit[i]})
	}
	sort.Sort(SortByDiff{tasks})
	sort.Ints(worker)
	for i := 1; i < len(tasks); i++ {
		tasks[i].Profit = max(tasks[i].Profit, tasks[i-1].Profit)
	}
	fmt.Printf("tasks = %v worker = %v\n", tasks, worker)
	for _, w := range worker {
		for index < len(difficulty) && w >= tasks[index].Difficulty {
			index++
		}
		fmt.Printf("tasks【index】 = %v\n", tasks[index])
		if index > 0 {
			res += tasks[index-1].Profit
		}
	}
	return res
}