成都 企业 网站建设百度竞价排名平台

1、题目描述
一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目。现在给你两个长度一样的数组，starts数组代码每个会议开始的时间，ends数组代表每个会议结束的时间。
在给你一个当前时间，请你求出当日可以利用会议室宣讲的最大值

思路分析：
1.按照最早开始的会议排序，最早开始的优先。
2.按照最短时间排序，时间最短的优先。
3.按照最早结束排序，最早结束的优先。
贪心算法是纯粹的积累经验类型的算法思想，贪心策略的正确性证明是非常困难的，几乎不可能证明正确性，因此，只能通过对数器进行验证。同时，可以举反例排除错误的贪心策略。
比如上面的：
1.如果最早开始的会议时间是最长呢？直接怼一天的话，显然不合理对吧？
2.如果最短的会议在中间呢？导致它前面的时间浪费了，后面的时间可能正好差一点不够一个会议，这样也很浪费，肯定不是最优解。
因此，排除掉1和2，此题的最优贪心算法应该就是3。

解题思路：
是按照项目完成时间，从前到后排序，先做最早结束的项目，然后淘汰掉不能再做的项目

public static class Program {public int start;public int end;public Program(int start, int end) {this.start = start;this.end = end;}
}
// 会议的开始时间和结束时间，都是数值，不会 < 0
public static int bestArrange2(Program[] programs) {Arrays.sort(programs, new ProgramComparator());int timeLine = 0;int result = 0;// 依次遍历每一个会议，结束时间早的会议先遍历for (int i = 0; i < programs.length; i++) {if (timeLine <= programs[i].start) {result++;timeLine = programs[i].end;}}return result;
}public static class ProgramComparator implements Comparator<Program> {@Overridepublic int compare(Program o1, Program o2) {return o1.end - o2.end;}}