826. Most Profit Assigning Work #

Problem #

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]

Problem Summary #

This problem examines the sliding window approach, and is also related to sorting.

Given a group of jobs, each job has a certain difficulty, and each job also has a corresponding profit after completion (a harder job does not necessarily have the highest profit). There is a group of workers, and each person can handle jobs of different difficulties. The task is to output the maximum profit after this group of workers completes jobs.

Solution Approach #

First sort the jobs by difficulty, and also sort the workers by their ability to handle job difficulty. Use an array to record, for each index i, the maximum profit that can currently be achieved. To calculate this profit, you only need to start from index 1 and compare each job’s profit with the previous one in order (because after sorting, the difficulty increases sequentially). After obtaining this array whose difficulty increases sequentially and which records the maximum profit, you can calculate the final result. Traverse the worker array once; if a worker’s ability is greater than the job difficulty, add this maximum profit. After traversing the worker array, the final result is the maximum profit.

Code #

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
}