没有A出来,考完后自己又思考了一下。用的是贪心+单调栈,不知道对不对,大家可以讨论一下。
package shun_feng;
import java.util.*;
public class Main1 {
static class Task implements Comparator<Task> {
public int l;
public int r;
public int w;
public Task(int l, int r, int w) {
this.l = l;
this.r = r;
this.w = w;
} public int compare(Task o1, Task o2) {
return o1.l - o2.l;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
Task[] tasks = new Task[n];
for (int i = 0; i < n; i++) {
int l = in.nextInt();
int r = in.nextInt();
int w = in.nextInt();
Task task = new Task(l, r, w);
tasks[i] = task;
}
Arrays.sort(tasks, ((o1, o2) -> o1.l - o2.l));
int res = 0;
LinkedList<Task> stack = new LinkedList<>();
int index = 0;
stack.push(tasks[index++]);
while (index < tasks.length) {
if (stack.peek().r <= tasks[index].l) {
stack.push(tasks[index]);
} else {
Task peek = stack.pop();
stack.push(peek.w > tasks[index].w ? peek : tasks[index]);
}
index++;
}
while (!stack.isEmpty()) {
res += stack.pop().w;
}
System.out.println(res);
}
}
}
这样写过了测试用例。 就是先按照每个任务的起始时间对任务进行排序。对于当前任务,如果它的结束时间早于下一个任务的开始时间,就把下个任务入栈,如果晚于,就将当前任务出栈,比较谁的赏金大,再入栈。
最后栈里面存储的都是互不冲突的任务(冲突的任务已经取赏金最大值入栈了),出栈累加赏金即可。请问这样做对么?

全部评论
(2) 回帖