没有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) 回帖