题目：一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间。你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回最多的宣讲场次。
方法一：暴力枚举，大概思路就是枚举每一个会议，如果遍历到的会议的开始时间晚于当前的时间点，说明这个会议可以举行。所以将其剔除掉。然后，剔除掉的会议的结束时间就是当前的时间点，剩下的会议都这么枚举，一定会有能安排的最大会议数量的可能性。 注意，因为会每次复制一个新的会议数组，所以不用remove来恢复现场。此方法只是为了测试贪心的正确性。
方法二：贪心，定义一个自己的比较器，排序规则就是谁的结束时间早谁排在前面。然后遍历所有的会议，结束时间早的会议会被先遍历到，如果当前会议的开始时间晚于当前的时间，说明可以进行这个会议。如果不能进行，就会跳过
package com.harrison.class09; import java.util.Arrays; import java.util.Comparator; public class Code02_BestArrange { public static class Program { public int start; public int end; public Program(int s, int e) { start = s; end = e; } } // 按会议结束时间早排序 public static class ProgramComparator implements Comparator<Program> { public int compare(Program o1, Program o2) { return o1.end - o2.end; } } // ans 最多能安排的会议个数 // timeLine 当前来到的时间 public static int bestArrange1(Program[] programs) { Arrays.sort(programs, new ProgramComparator()); int ans = 0; int timeLine = 0; for (int i = 0; i < programs.length; i++) { // 如果当前来到的时间点 比 当前会议开始时间 早 说明可以开始这个会议 // 那么能安排的会议个数+1 // 当前时间来到当前会议的结束时间 if (timeLine <= programs[i].start) { ans++; timeLine = programs[i].end; } } return ans; } // 还剩下的会议都放在programs里 // done之前已经安排了多少会议的数量 // timeLine目前来到的时间点是什么 // 目前来到timeLine的时间点，已经安排了done多的会议，剩下的会议programs可以自由安排 // 返回能安排的最多会议数量 public static int process(Program[] programs, int done, int timeLine) { if (programs.length == 0) {// 没有要安排的会议了，就返回已经安排好的会议个数 return done; } // if没中，说明还剩下会议 int max = done; // 当前安排的会议是什么会，每一个都枚举 for (int i = 0; i < programs.length; i++) { if (programs[i].start >= timeLine) {// 当前会议的开始时间晚于现在的时间点 Program[] next = copyButExcept(programs, i); max = Math.max(max, process(next, done + 1, programs[i].end)); } } return max; } // 在programs数组里剔除掉第i个会议 public static Program[] copyButExcept(Program[] programs, int i) { Program[] ans = new Program[programs.length - 1]; int index = 0; for (int k = 0; k < programs.length; k++) { if (k != i) { ans[index++] = programs[k]; } } return ans; } // 暴力！所有情况都尝试！ public static int bestArrange2(Program[] programs) { if (programs == null || programs.length == 0) { return 0; } return process(programs, 0, 0); } public static Program[] generatePrograms(int programSize, int timeMax) { Program[] ans = new Program[(int) (Math.random() * (programSize + 1))]; for (int i = 0; i < ans.length; i++) { int r1 = (int) (Math.random() * (timeMax + 1)); int r2 = (int) (Math.random() * (timeMax + 1)); if (r1 == r2) { ans[i] = new Program(r1, r1 + 1); } else { ans[i] = new Program(Math.min(r1, r2), Math.max(r1, r2)); } } return ans; } public static void main(String[] args) { int programSize = 12; int timeMax = 20; int timeTimes = 1000000; for (int i = 0; i < timeTimes; i++) { Program[] programs = generatePrograms(programSize, timeMax); if (bestArrange1(programs) != bestArrange2(programs)) { System.out.println("Oops!"); } } System.out.println("finish!"); } }
