贪心算法-宣讲会问题

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。
也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 

贪心算法的在笔试时的解题套路
1，实现一个不依靠贪心策略的解法X，可以用最暴力的尝试
2，脑补出贪心策略A、贪心策略B、贪心策略C..
3，用解法X和对数器，去验证每一个贪心策略，用实验的方式得知哪个贪心策略正确
4，不要去纠结贪心策略的证明 

题目一：

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

solution：

先把会议按照结束时间从小到大排序，
优先安排会议结束早的宣讲，然后删除和此会议时间冲突的宣讲，再从剩余的宣讲中选择结束时间早的宣讲......

算法代码：

public class BestArrange {

    //宣讲项目模型
    public static class Program {
        public int start;
        public int end;

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

    //自定义比较器
    public static class ProgramComparator implements Comparator<Program> {
        @Override
        public int compare(Program o1, Program o2) {
            return o1.end - o2.end;
        }

    }

    /**
     * 贪心算法：宣讲会议安排
     * @param programs ：所有的会议
     * @param start ：目前来到的时间点
     * @return ：返回最多安排次数
     */
    public static int bestArrange(Program[] programs, int start) {
        Arrays.sort(programs, new ProgramComparator()); //先把所有的项目根据结束时间谁早进行排序
        System.out.println("排序后的会议为：");
        for (int i = 0; i < programs.length; i++) {
            System.out.print(programs[i]+" ");
        }
        System.out.println();
        int result = 0;
        //从左往右依次遍历所有的会议
        for (int i = 0; i < programs.length; i++) {
            if (start <= programs[i].start) { //现在来到的时间点有没有早于当前考虑会议的开始时间
                result++;
                start = programs[i].end; // start来到会议结束的时候
            }
        }
        return result;
    }   
}

测试：

package Algorithms.greed;

import java.util.Arrays;
import java.util.Comparator;

public class BestArrange {

    //宣讲项目模型
    public static class Program {
        public int start;
        public int end;

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

        @Override
        public String toString() {
            return "Program{" +
                    "start=" + start +
                    ", end=" + end +
                    '}';
        }
    }

    //自定义比较器
    public static class ProgramComparator implements Comparator<Program> {
        @Override
        public int compare(Program o1, Program o2) {
            return o1.end - o2.end;
        }

    }

    /**
     * 贪心算法：宣讲会议安排
     * @param programs ：所有的会议
     * @param start ：目前来到的时间点
     * @return ：返回最多安排次数
     */
    public static int bestArrange(Program[] programs, int start) {
        Arrays.sort(programs, new ProgramComparator()); //先把所有的项目根据结束时间谁早进行排序
        System.out.println("排序后的会议为：");
        for (int i = 0; i < programs.length; i++) {
            System.out.println(programs[i]+" ");
        }
        System.out.println();
        int result = 0;
        int n = 0;
        //从左往右依次遍历所有的会议        
        for (int i = 0; i < programs.length; i++) {
            if (start <= programs[i].start) { //现在来到的时间点有没有早于当前考虑会议的开始时间
                result++;
                n++;
                System.out.println("第 "+n+" 场会议为"+programs[i]);
                start = programs[i].end; // start来到会议结束的时候
            }
        }
        return result;
    }

    public static void main(String[] args) {

        Program[] programs = {new Program(3, 10),new Program(3, 5),new Program(4, 11),
                new Program(7, 13),new Program(8, 12),new Program(14, 15)};
        int maxNumbers = bestArrange(programs, 2);
        System.out.println("会议的最大安排次数为："+maxNumbers);
    }
}

/**
 * 排序后的会议为：
 * Program{start=3, end=5}
 * Program{start=3, end=10}
 * Program{start=4, end=11}
 * Program{start=8, end=12}
 * Program{start=7, end=13}
 * Program{start=14, end=15}
 *
 * 第 1 场会议为Program{start=3, end=5}
 * 第 2 场会议为Program{start=8, end=12}
 * 第 3 场会议为Program{start=14, end=15}
 * 会议的最大安排次数为：3
 */