asp网站建设中期报告,wordpress二次主题,知名企业官网设计公司,无锡网络推广哪家好1、题目描述 一些项目要占用一个会议室宣讲#xff0c;会议室不能同时容纳两个项目。现在给你两个长度一样的数组#xff0c;starts数组代码每个会议开始的时间#xff0c;ends数组代表每个会议结束的时间。 在给你一个当前时间#xff0c;请你求出当日可以利用会议室宣讲的…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 ComparatorProgram {Overridepublic int compare(Program o1, Program o2) {return o1.end - o2.end;}}
