LeetCode 826. Most Profit Assigning Work

题目链接 Most Assigning Work



题意读完有点像背包问题,只是没有背包空间限制

一开始我的思路是先构建一个 Task 的 list,task一个成员变量 是 difficulty,另一个成员变量 是 profit,然后按照 difficulty 排序,且,value 是该 difficulty 下的最大 profit

然后对每个 worker 去在刚才的 list 里面二分查找,找到最接近的那个 item就是最大 profit

这种时间复杂度很明显是O(NlogN),只 beat 了37.5%的人

独立做完之后看到评论区lee215大神的解法,做法是先和我一样构建 list,只是他的 list 的所有 value 并不需要是该 difficulty 下的最大 value,只要是该 difficulty 的对应 value 就可以

然后对 worker 也做排序,然后一样,找出每个 worker 的最大值,但是他的方法只需要便利一遍 list 和 worker 就能求出最大值, beat 60.72%

talk is cheap, show me the code

this is idea1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution {
static class Task {
private int difficulty;
private int profit;

public Task(int difficulty, int profit) {
this.difficulty = difficulty;
this.profit = profit;
}

public int getDifficulty() {
return difficulty;
}

public int getProfit() {
return profit;
}
}
public static int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
List<Task> tasks = new ArrayList<>();
for (int i = 0; i < difficulty.length; i++) {
tasks.add(new Task(difficulty[i], profit[i]));
}
tasks.sort(Comparator.comparing(Task::getDifficulty));

Map<Integer, Integer> map = new HashMap<>();
int currMax = tasks.get(0).getProfit();
for (int i = 0; i < difficulty.length; i++) {
Task task = tasks.get(i);
if (currMax < task.getProfit()) {
currMax = task.getProfit();
}
map.put(task.difficulty, currMax);
}

int result = 0;
for (int diff : worker) {
int start = 0;
int end = profit.length - 1;
boolean left = true;
while (start < end) {
int mid = (start + end) / 2;
if (tasks.get(mid).getDifficulty() > diff) {
left = true;
end = mid - 1;
} else if (tasks.get(mid).getDifficulty() < diff) {
left = false;
start = mid + 1;
} else {
break;
}
}
if (start == end) {
if (left) {
int newDiff = tasks.get(end).getDifficulty();
if (diff >= newDiff) {
result += map.get(newDiff);
} else {
result += end > 0 ? map.get(tasks.get(end - 1).difficulty) : 0;
}
} else {
if (diff < tasks.get(end).getDifficulty()) {
result += map.get(tasks.get(end - 1).getDifficulty());
} else {
result += map.get(tasks.get(end).getDifficulty());
}
}
} else if (start < end) {
result += map.get(diff);
} else {
result += end >= 0 ? map.get(tasks.get(end).getDifficulty()) : 0;
}
}
return result;

}
}

this is idea2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public static int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
class Job {
private int difficulty;
private int profit;

public Job(int difficulty, int profit) {
this.difficulty = difficulty;
this.profit = profit;
}

public int getDifficulty() {
return difficulty;
}

public int getProfit() {
return profit;
}
}
List<Job> list = new ArrayList<>();
for (int i = 0; i < difficulty.length; i++) {
list.add(new Job(difficulty[i], profit[i]));
}
list.sort(Comparator.comparingInt(Job::getDifficulty));
Arrays.sort(worker);
int max = 0;
int i = 0;
int result = 0;
for (int work : worker) {
while (i < difficulty.length && work >= list.get(i).getDifficulty()) {
max = Math.max(max, list.get(i++).getProfit());
}
result += max;
}
return result;
}

}
月月说要给我打赏,就还是放了二维码,😝