leetcode贪心策略

分金条

这是一种求最小花费的问题，而且总共的代价是由子代价累加得到的，可以使用哈夫曼树来解决。

public int min_money(int[] arr){
    //定义一个小顶堆，每次取出两个最小的元素作为哈夫曼树的构建
    PriorityQueue<Integer> data = new PriorityQueue<>();
    for(int i=0;i<arr.length;i++){
        data.add(arr[i]);
    }
    //构建哈夫曼树，每次取出两个最小元素作为合并的两个节点，并将合并的值重新放入堆中
    int cur = 0;
    int res = 0;
    while(data.size()>1){
        cur = data.poll()+data.poll();
        data.add(cur);
        res+= cur;
    }
    return res;
}

502. IPO

public class Node{
    private int cost;
    private int profit;
    public Node(int cost,int profit){
        this.cost = cost;
        this.profit = profit;
    }
}
public class MinHeapComparator implements Comparator<Node> {
    @Override
    public int compare(Node o1, Node o2) {
        return o1.cost-o2.cost;
    }
}
public class MaxHeapComparator implements Comparator<Node>{
    @Override
    public int compare(Node o1, Node o2) {
        return o2.profit-o1.profit;
    }
}
public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
    //小顶堆，按照花费排序
    PriorityQueue<Node> minCostHeap = new PriorityQueue<>(new MinHeapComparator());
    //大顶堆，按照收益排序
    PriorityQueue<Node> maxProfitHeap = new PriorityQueue<>(new MaxHeapComparator());
    for(int i=0;i<Profits.length;i++){
        Node node = new Node(Capital[i],Profits[i]);
        minCostHeap.add(node);
    }

    /***将minCostHeap中所有<=W的元素全部移到MaxProfit中，这样，MaxProfit中存储的就是所有小于总资产的可挑选的项目，
         * 并且按照收益排序，因此，直接获取MaxProfit堆顶元素即可，直到k次项目选择完毕，或者是大顶堆没有元素(没有项目<=手中的资产)*/
    for(int i =0;i<k;i++){
        while(!minCostHeap.isEmpty()&&minCostHeap.peek().cost<=W){
            maxProfitHeap.add(minCostHeap.poll());
        }
        if(maxProfitHeap.size()<1){
            return W;
        }
        W+=maxProfitHeap.poll().profit;
    }
    return W;
}

会议室项目宣讲

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

贪心策略：

• 开始时间最早的项目先安排。反例：开始时间最早，但持续时间占了一整天，其他项目无法安排。
• 持续时间最短的先安排。反例：这样安排会导致结束时间在此期间和开始时间在此期间的所有项目不能安排。
• 最优策略：最先结束的项目先安排。

public class Program{
    private int start;
    private int end;
    public Program(int start,int end){
        this.start = start;
        this.end = end;
    }

}
public class ProgramComparator implements Comparator<Program>{
    @Override
    public int compare(Program o1, Program o2) {
        return o1.end-o2.end;
    }
}
/**
     * 以结束时间最早作为贪心策略
     * 因此，每次需要取出大于等于上一次结束时间的且结束时间最小的项目
     * */
public int bestArrange(Program[] programs, int start) {
    Arrays.sort(programs,new ProgramComparator());
    int result = 0;
    for(int i=0;i<programs.length;i++){
        if(start<=programs[i].start){
            result++;
            start = programs[i].end;
        }
    }
    return result;
}