贪心算法

在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫作贪心算法

也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解

会议室问题

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

贪心策略：谁结束早安排谁

class Program{
    int start;
    int end;
    
    public Program(int start, int end) {
        this.start = start;
        this.end = end;
    }
}
class ProgramComparator implements Comparator<Program> {//比较器按照谁结束的早放在前面
    
    @Override
    public int compare(Program o1, Program o2) {
        return o1.end - o2.end;
    }
}

public static int bestArrange(Program[] programs, int timePoint) {
    Arrays.sort(programs, new ProgramComparator());
    int result = 0;
    //遍历所有会议
    for (int i = 0; i< program.length; i++){
        if (timePoint <= programs[i].start) {
            result++;
            timePoint = programs[i].end;
        }
    }
    return result;
}

金条问题（哈夫曼编码）

一个金条，不管怎么分割，分割的花费和它的长度一致

现在给出一个数组 {10,20,30}，金条长度为其之和60，怎么分才花费最少？

贪心策略：把所有数放入小根堆，每次弹出两个数，结合两数后再放入小根堆，每次结合的数的值累加

public static int lessMoney(int[] arr) {
    PriorityQueue<Integer> pQ = new PriorityQueue<>();
    for (int i = 0; i < arr.lengthg; i++) {
        pQ.add(arr[i]);
    }
    int sum = 0;
    int cur = 0;
    while (pQ.size() > 1) {
        cur = pQ.poll() + pQ.poll();
        sum += cur;
        pQ.add(cur);
    }
    return sum;
}

项目利润

贪心思路：一个大根堆，一个小根堆，小根堆根据花费排序，大根堆根据利润排序，刚开始所有元素进入小根堆，然后弹出<=启动资金的项目，进入大根堆，大根堆中弹出利润最高

class Node{
    public int p;
    public int c;
    
    public Node(int p, int c){
        p = this,p;
        c = this.c;
    }
}
class MinCostComparator implements Comparator<Node> {
    public int compare(Node o1, Node o2) {
        return o1.c - o2.c;
    }
}
class MaxProfitComparator implements Comparator<Node> {
    public int compare(Node o1, Node o2) {
        return o2.p - o1.p;
    }
}
public static int profitMost(int[] costs, int[] profits, int k, int m) {
     PriorityQueue<Integer> cost = new PriorityQueue<>();
     PriorityQueue<Integer> profit = new PriorityQueue<>();
     //所有项目加入小根堆
     for (int i = 0; i < costs.length; i++) {
		cost.add(new Node(profits[i], costs[i]) );
     }
     for (int i = 0; i < k; i++) {
         while(!cost.isEmpty() && cost.peek().c <= m) {
             profit.add(cost.poll());
         }
         if (profit.isEmpty()) {
             return m;
         }
         m += profit.poll();
     }
    return m;
}

堆的学习->一个数据流中，随时取得中位数

1. 第一个数直接大根堆
2. cur <= 大根堆第一个，是就进大根堆，否则进小根堆
3. 看大根堆和小根堆的大小，size较大的比较小的size大到2，size大的那个堆顶弹出进入另一个
4. 效果：较大的数在小根堆，较小的在大根堆

字符串拼接产生最小字典序

比较ab和ba的字典序，谁小谁在前