贪心算法

一.基本概念

求解问题时，局部上得到最优解然后得到全局的最优解。

例如：分钱问题
用若干张5元，10元，15元的零钱，去凑齐25块，要求拿出的总张数足够少。
组合方式有以下几种:

• 5+5+5+5+5=25
• 5+5+5+10=25
• 5+5+15=25
  .....

使用贪心法解决
要求张数最少则零钱的面额要足够大
使用一张15的零钱，剩10
使用一张10的零钱，完成
则结果为：15+10=25，使用一张15的和一张10块的零钱凑齐25，使用的张数最少。

二.贪心算法必须具备无后效性

无后效性:即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
如下:这个问题使用贪心算法不能得到争取答案
这个二叉树上的每一个节点都有分数，选择一条从根节点到叶子节点的路径，使得到的分数最多。
使用贪心算法得到的路径 :3->7(7>4)->11(11>9) 和为21

但是3->4->20 和27 比21大

image.png

三.经典问题--工作安排问题

有一些工作Job，每个工作都有开始时间和结束时间，现在将这些工作加入一个集合，要求集合中的Job事件没有重合，而且集合中Job的数量尽可能多

思路

1. 将job按照结束时间从小到大排序，得到集合a1
2. 将集合a1中第一个Job加入到最终集合a2中， 遍历排序后的集合a1，将不与前一个Job的时间不重合的Job加入到a2中

public class Job {
    private int startTime;
    private int endTime;

    public Job(int startTime, int endTime) {
        this(startTime, endTime);
    }

    public int getStartTime() {
        return startTime;
    }

    public int getEndTime() {
        return endTime;
    }

}

   public static List<Job> getMaxSchedulerJobs(List<Job> allJobs) {

        if (allJobs == null || allJobs.size() <= 1) {
            return allJobs;
        }

        //sorted by end time
        allJobs.sort(new Comparator<Job>() {
            @Override
            public int compare(Job job1, Job job2) {
                return job1.getEndTime() - job2.getEndTime();
            }
        });

        List<Job> resultJobs = new ArrayList<>();
        Job preJob = allJobs.get(0);
        resultJobs.add(preJob);

        //select job
        for (int i = 1; i < allJobs.size(); i++) {
            Job nowJob = allJobs.get(i);
            if (preJob.getEndTime() <= nowJob.getStartTime()) {
                preJob = nowJob;
                resultJobs.add(preJob);
            }
        }

        return resultJobs;

    }