<贪心>会议室宣讲&&哈弗曼树&&切金条&&LeetCode502IPO

一、会议室宣讲

一些项目要占用一个会议室宣讲, 会议室不能同时容纳两个项目的宣讲。 给你每一个项目开始的时间和结束的时间(给你一个数组, 里面 是一个个具体的项目), 你来安排宣讲的日程, 要求会议室进行 的宣讲的场次最多。 返回这个最多的宣讲场次。

这个也是一个贪心算法,优先考虑的是宣讲会结束时间早的那个。

二、哈弗曼树&&切金条

一块金条切成两半, 是需要花费和长度数值一样的铜板的。 比如长度为20的 金条, 不管切成长度多大的两半, 都要花费20个铜板。 一群人想整分整块金 条, 怎么分最省铜板?

例如,给定数组{10,20,30}, 代表一共三个人, 整块金条长度为10+20+30=60. 金条要分成10,20,30三个部分。 如果, 先把长度60的金条分成10和50, 花费60 再把长度50的金条分成20和30,花费50 一共花费110铜板。但是如果, 先把长度60的金条分成30和30, 花费60 再把长度30金条分成10和20, 花费30 一共花费90铜板。输入一个数组, 返回分割的最小代价。

 //最小堆的比较器
    public static class minHeapComparator implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    }

    public static int lessMoney(int[] arr) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new minHeapComparator());
        for (int num : arr){
            priorityQueue.add(num);
        }
        int sum = 0;
        int cur = 0;
        while (priorityQueue.size()>1){
           cur = priorityQueue.poll() + priorityQueue.poll();
           sum += cur;
           priorityQueue.offer(cur);
        }
        return sum;
    }

采用一个最小堆,每次取出两个数,把和再添加到最小堆,以此往复。

实际上java默认的就是建立最小堆。

三、Leetcode502 IPO

输入: 参数1, 正数数组costs 参数2, 正数数组profits 参数3,正数k 参数4, 正数m costs[i]表示i号项目的花费 profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润) k表示你不能并行、 只能串行的最多做k个项目 m表示你初始的资金说明: 你每做完一个项目, 马上获得的收益, 可以支持你去做下一个 项目。

输出: 你最后获得的最大钱数

Input: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].

Output: 4

Explanation:
             Since your initial capital is 0, you can only start the project indexed 0.
             After finishing it you will obtain profit 1 and your capital becomes 1.
             With capital 1, you can either start the project indexed 1 or the project indexed 2.
             Since you can choose at most 2 projects, you need to finish the project
                    indexed 2 to get the maximum capital.
             Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

采用一个最大堆和一个最小堆。由于两个数组都要放入堆里,那么怎么两个数组的相应元素的对应问题需要考虑,于是这里是新定义一种数据类型:psNode

   public static class psNode{
        int profits;
        int costs;
        public psNode(int profits, int cotes) {
            this.profits = profits;
            this.costs = cotes;
        }
    }

    public static class ProfitsMaxHeap implements Comparator<psNode>{
        @Override
        public int compare(psNode o1, psNode o2) {
            return o2.profits - o1.profits;
        }
    }

    public static class CostsMinHeap implements Comparator<psNode>{
        @Override
        public int compare(psNode o1, psNode o2) {
            return o1.costs - o2.costs;
        }
    }



    public int findMaximizedCapital(int k, int W, int[] Profits, int[] Costs) {
        psNode [] psNodes = new psNode[Profits.length];
        for ( int i = 0;i < Profits.length;i++){
            psNodes[i] = new psNode(Profits[i],Costs[i]);
    }

        PriorityQueue<psNode> profitsHeap = new PriorityQueue<>(new ProfitsMaxHeap());
        PriorityQueue<psNode> costsHeap = new PriorityQueue<>(new CostsMinHeap());

        for (psNode node : psNodes){
            costsHeap.offer(node);
        }

        for (int i = 0; i < k; i++) {
            while (!costsHeap.isEmpty() && costsHeap.peek().costs <= W){
                profitsHeap.offer(costsHeap.poll());
            }
            if (profitsHeap.isEmpty()) return W;
            W += profitsHeap.poll().profits;
        }
        return W;
    }

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券