首页 > 顺丰笔试_赏金猎人
头像
Galip
编辑于 2020-08-20 22:06
+ 关注

顺丰笔试_赏金猎人

没有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) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐