image.png

image.png

用来验证的暴力解

  1. public static class Program{
  2. public int start;
  3. public int end;
  4. public Program(int start, int end) {
  5. this.start = start;
  6. this.end = end;
  7. }
  8. }
  9. /*
  10. 暴力解
  11. */
  12. public static int bestArrange(Program[] programs) {
  13. if (programs == null || programs.length == 0) {
  14. return 0;
  15. }
  16. return process(programs, 0, 0);
  17. }
  18. /*
  19. 目前来到timeLine的时间点,已经安排了done多的会议,剩下的会议programs可以自由安排
  20. */
  21. private static int process(Program[] programs, int done, int timeLine) {
  22. if (programs.length == 0) {
  23. return done;
  24. }
  25. // 还有会议可以选择
  26. int max = done;
  27. // 当前安排的会议是什么会,每个都枚举
  28. for (int i = 0; i < programs.length; i++) {
  29. if (programs[i].start >= timeLine) {
  30. Program[] next = copyButExcept(programs, i);
  31. max = Math.max(max, process(next, done + 1, programs[i].end));
  32. }
  33. }
  34. return max;
  35. }
  36. private static Program[] copyButExcept(Program[] programs, int i) {
  37. Program[] ans = new Program[programs.length - 1];
  38. int index = 0;
  39. for (int k = 0; k < programs.length; k++) {
  40. if (k != i) {
  41. ans[index++] = programs[k];
  42. }
  43. }
  44. return ans;
  45. }

贪心

  1. /*
  2. 法二:按每场的结束时间
  3. */
  4. public static int bestArrange2(Program[] programs) {
  5. Arrays.sort(programs, (o1, o2) -> o1.end - o2.end);
  6. int timeLine = 0;
  7. int result = 0;
  8. for (int i = 0; i < programs.length; i++) {
  9. if (programs[i].start >= timeLine) {
  10. result++;
  11. timeLine = programs[i].end;
  12. }
  13. }
  14. return result;
  15. }