MostProfitAssigningWork [source code]
public class MostProfitAssigningWork {
static
/****************************************************************************/
class Solution {
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
Job[] jobs = new Job[difficulty.length];
for (int i = 0; i < difficulty.length; i++) {
jobs[i] = new Job (difficulty[i], profit[i]);
}
Arrays.sort (jobs, (a, b) -> a.difficulty - b.difficulty);
int max_profit = -1;
Map<Integer, Integer> rewards = new HashMap<> ();
for (int i = 0; i < jobs.length; i++) {
max_profit = Math.max (max_profit, jobs[i].profit);
jobs[i].profit = max_profit;
rewards.put (jobs[i].difficulty, max_profit);
}
int res = 0;
for (int i = 0; i < worker.length; i++) {
int pos = binarySearch (jobs, worker[i]);
if (pos < difficulty.length && jobs[pos].difficulty == worker[i]) {
res += rewards.get (jobs[pos].difficulty);
} else {
if (pos == 0)
continue;
res += rewards.get (jobs[pos - 1].difficulty);
}
}
return res;
}
int binarySearch (Job[] jobs, int worker) {
int lo = 0, hi = jobs.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (jobs[mid].difficulty == worker)
return mid;
else if (worker < jobs[mid].difficulty)
hi = mid - 1;
else
lo = mid + 1;
}
return lo;
}
static class Job {
int difficulty, profit;
Job (int d, int p) {
this.difficulty = d;
this.profit = p;
}
public String toString () {
return String.format ("%d/%d", this.difficulty, this.profit);
}
}
}
/****************************************************************************/
public static void main(String[] args) {
MostProfitAssigningWork.Solution tester = new MostProfitAssigningWork.Solution();
int[][] inputs = {
{2,4,6,8,10}, {10,20,30,40,50}, {4,5,6,7}, {100},
{85,47,57}, {24,66,99}, {40,25,25}, {0},
{13,37,58}, {4,90,96}, {34,73,45}, {190},
{23,30,35,35,43,46,47,81,83,98}, {8,11,11,20,33,37,60,72,87,95}, {95,46,47,97,11,35,99,56,41,92}, {553},
{68,35,52,47,86}, {67,17,1,81,3}, {92,10,85,84,82}, {324},
{66,1,28,73,53,35,45,60,100,44,59,94,27,88,7,18,83,18,72,63}, {66,20,84,81,56,40,37,82,53,45,43,96,67,27,12,54,98,19,47,77}, {61,33,68,38,63,45,1,10,53,23,66,70,14,51,94,18,28,78,100,16}, {1392},
};
for (int i = 0; i < inputs.length / 4; i++) {
System.out.println (Printer.separator ());
int[] difficulty = inputs[4 * i], profit = inputs[4 * i + 1], worker = inputs[4 * i + 2];
int ans = inputs[4 * i + 3][0], output = tester.maxProfitAssignment (difficulty, profit, worker);
System.out.printf ("%s\n%s\n%s\n%s\n%d\n",
Printer.array (difficulty), Printer.array (profit), Printer.array (worker), Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
看起来不是很难; 应该是先sort difficulty, 然后二分查找; 然后为了保证能够用difficulty找到profit, 所以可能要维护一个Map;
好像没有说过difficulty里面不能有重复? 不对, 仔细想了一下, 他题目给的这个例子有点迷惑性, 看起来好像是默认难度越高的任务, profit越多一样, 但是实际上最后未必是这样的;
干脆把difficulty和profit封装起来, 想不到更好的办法了;
重复difficulty好像不用管, 最后维护一个就行了;
很有意思的一个题目; 被test4给break了, 发现这个题目的testcase都写的相当仔细;
这题错了好多次. 总体来说是有思路的, 只能说还是基本功太差了, 各种写bug;
注意这里第二个循环里面, 我把当前的max放到了两个位置: jobs[i]里面, 和rewards这个Map里面; 一开始我认为这个Map是不必要的, 但是后面有一个test好像是专门把这个break掉了: 只是在Job本身里面存放自己能获得的最大profit好像不够; 具体怎么break的忘记了;
好像有点印象, 你看这个Map, 存的是一个difficulty=profit, 而不是针对某一个job; 所以如果比如difficulty 10本来能赚50, 那么后面突然又来了一个让difficulty 10能赚60, 那么前面这个刚刚拿了50就走的Job是不知道的; 所以只能用Map这个东西存一个全局的映射;
然后最后一个主循环, 二分这个返回回来的index, 我各种没有处理好, 好几个bug, 很丢人; 主要要注意的是如果这个pos返回回来是0或者N是怎么办: Sedgwick的二分写法最后这两个值都是有可能出现的; 然后就是hit和miss的区别; 真正写代码的时候还是一个先追求correct, 不要想太多; 就跟我这里这样, 就分开是hit和miss的判断; 然后两个特殊index也专门判断处理;
回头重新看这个题目真的是不难, 结果contest当时是失败了5次才AC;
UNFINISHED
editorial
Approach #1: Sorting Events [Accepted]
Intuition
We can consider the workers in any order, so let's process them in order of skill.
If we processed all jobs with lower skill first, then the profit is just the most profitable job we have seen so far.
Algorithm
We can use a "two pointer" approach to process jobs in order. We will keep track of best, the maximum profit seen.
For each worker with a certain skill, after processing all jobs with lower or equal difficulty, we add best to our answer.
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;
}
}
看完这个算法之后, 感觉我大部分的点都get到了, 但是最后这个二分, 好像不是必要的, 他这里最后这个做法就是规避掉了这个二分;
然后用这个point来完成了一个类似我的封装;
第二个循环应该是关键, 第一个循环就是一个简单的把d和p两个数组原样排序而已;
一个区别是他把worker也都sort了, 这个我是没有做的;
看了一下不是特别的复杂, 就是对每一个worker, 倒序找自己能胜任的最贵的工作; 不对, 是正序. 从最低difficulty开始找, 所以加入低difficulty的job有更高的profit, 这个max就不会错过(保存在了best里面).
大概这个方法还是可以的.
uwi: 6分钟...这个速度真的无语了, 这题我写了好久;
class Solution {
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
int n = difficulty.length;
int[][] dp = new int[n][];
for(int i = 0;i < n;i++){
dp[i] = new int[]{difficulty[i], profit[i]};
}
Arrays.sort(dp, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if(a[0] != b[0])return a[0] - b[0];
return -(a[1] - b[1]);
}
});
int[] xs = new int[n];
for(int i = 0;i < n;i++)xs[i] = dp[i][0];
for(int i = 1;i < n;i++){
dp[i][1] = Math.max(dp[i][1], dp[i-1][1]);
}
int ret = 0;
for(int w : worker){
int ind = Arrays.binarySearch(xs, w);
if(ind < 0)ind = -ind-2;
if(ind >= 0){
ret += dp[ind][1];
}
}
return ret;
}
}
比较奇怪的做法, job是profit降序排列; 哦不对, 是difficulty升序, 然后用profit降序来break tie, 这个应该是无所谓的;
xs应该是一个类似dp lookup的结果, 比如max so far这种的结构;
没错, 中间这个for循环就是在计算这个;
二分查找, 大概跟我的做法实际上是差不多的;
无非就是比我快而已 :)
Problem Description
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]
Difficulty:Medium
Total Accepted:586
Total Submissions:2.4K
Contributor:awice
Companies
netease
Related Topics
two pointers