最大的观影时间问题
作者：Grey
原文地址：
题目描述
一场电影开始和结束时间可以用一个小数组来表示
["07:30","12:00"]
已知有 2000 场电影开始和结束都在同一天，这一天从 00:00 开始到 23:59 结束
一定要选 3 场完全不冲突的电影来观看，返回最大的观影时间
如果无法选出 3 场完全不冲突的电影来观看，返回 -1
暴力解法
枚举前三场电影的所有的可能全排列，定义如下递归函数
int process1(int[][] movies, int index) 递归含义表示，从 index 开始到最后，任意选三场不冲突的电影，最大观影时间是多少。
首先是 base case，由于是枚举所有可能的排列，所以，任意三场都可能出现在 0，1，2 位置上，所以，base case 就是 index == 3 的时候，可以结算
当 index == 3 的时候，可以结算此时的 0， 1， 2 的电影情况，计算出最大观影时间
int start = 0; int watch = 0; for (int i = 0; i < 3; i++) { if (start > movies[i][0]) { return -1; } watch += movies[i][1] - movies[i][0]; start = movies[i][1]; } return watch; 否则，就是做全排列，全排列算法可以参考这篇博客
int ans = -1; for (int i = index; i < movies.length; i++) { swap(movies, index, i); ans = Math.max(ans, process1(movies, index + 1)); swap(movies, index, i); } return ans; 暴力解法完整代码如下
public static int maxEnjoy1(int[][] movies) { if (movies.length < 3) { return -1; } return process1(movies, 0); } public static int process1(int[][] movies, int index) { if (index == 3) { int start = 0; int watch = 0; for (int i = 0; i < 3; i++) { if (start > movies[i][0]) { return -1; } watch += movies[i][1] - movies[i][0]; start = movies[i][1]; } return watch; } else { int ans = -1; for (int i = index; i < movies.length; i++) { swap(movies, index, i); ans = Math.max(ans, process1(movies, index + 1)); swap(movies, index, i); } return ans; } } public static void swap(int[][] movies, int i, int j) { int[] tmp = movies[i]; movies[i] = movies[j]; movies[j] = tmp; } 优化后的递归解
首先，对电影进行排序，开始时间在前的排在前面，开始时间一样的，结束时间前的排在前面。
递归函数设计为
int process2（int[][] movies, int index, int time, int rest) 递归含义表示：从 index 一直到最后一部电影，时间点从 0 开始，rest 表示还剩几部电影要选，得到的最大观影时间是多少。
所以 process2(int[][] movies, 0, 0, 3) 就是原题答案。
接下来是 base case，
如果 index == movies.length 表示没有电影可以选，此时，如果 rest == 0 ，表示正好不需要继续选电影，此时可以返回最大观影时间是 0， 否则，返回 -1 ，表示之前的决策有问题。
接下来是普遍情况，有两种决策：
决策一，可以不选 index 位置的电影，直接去 index + 1 位置做决策，即
int p1 = process2(movies, index + 1, time, rest); 决策二，选择 index 位置的电影，但是这个选择有条件，即： movies[index][0] >= time && rest > 0，表示当前电影的开始时间在 time 之后，且剩余要选择的电影大于 0，才能选。否则直接返回 -1，说明这种决策无效，即
// 电影的开始时间，要小于规定的time时间，且可选的电影要大于0 int next = movies[index][0] >= time && rest > 0 ? process2(movies, index + 1, movies[index][1], rest - 1) : -1; // 如果上述决策是-1，那么可能性2就是-1，如果不是-1，则继续去下一个位置选择。 int p2 = next != -1 ? (movies[index][1] - movies[index][0] + next) : -1; 综上所述，完整代码如下
public static int maxEnjoy2(int[][] movies) { Arrays.sort(movies, (a, b) -> a[0] != b[0] ? (a[0] - b[0]) : (a[1] - b[1])); return process2(movies, 0, 0, 3); } public static int process2(int[][] movies, int index, int time, int rest) { if (index == movies.length) { return rest == 0 ? 0 : -1; } int p1 = process2(movies, index + 1, time, rest); int next = movies[index][0] >= time && rest > 0 ? process2(movies, index + 1, movies[index][1], rest - 1) : -1; int p2 = next != -1 ? (movies[index][1] - movies[index][0] + next) : -1; return Math.max(p1, p2); } 使用对数器对上述两种算法进行多次测试，测试通过
import java.util.Arrays; public class Code_WatchMovieMaxTime { // 暴力方法，枚举前三场所有的可能全排列 public static int maxEnjoy1(int[][] movies) { if (movies.length < 3) { return -1; } return process1(movies, 0); } public static int process1(int[][] movies, int index) { if (index == 3) { int start = 0; int watch = 0; for (int i = 0; i < 3; i++) { if (start > movies[i][0]) { return -1; } watch += movies[i][1] - movies[i][0]; start = movies[i][1]; } return watch; } else { int ans = -1; for (int i = index; i < movies.length; i++) { swap(movies, index, i); ans = Math.max(ans, process1(movies, index + 1)); swap(movies, index, i); } return ans; } } public static void swap(int[][] movies, int i, int j) { int[] tmp = movies[i]; movies[i] = movies[j]; movies[j] = tmp; } // 优化后的递归解 public static int maxEnjoy2(int[][] movies) { Arrays.sort(movies, (a, b) -> a[0] != b[0] ? (a[0] - b[0]) : (a[1] - b[1])); return process2(movies, 0, 0, 3); } public static int process2(int[][] movies, int index, int time, int rest) { if (index == movies.length) { return rest == 0 ? 0 : -1; } int p1 = process2(movies, index + 1, time, rest); int next = movies[index][0] >= time && rest > 0 ? process2(movies, index + 1, movies[index][1], rest - 1) : -1; int p2 = next != -1 ? (movies[index][1] - movies[index][0] + next) : -1; return Math.max(p1, p2); } // 记忆化搜索的动态规划 // 为了测试 public static int[][] randomMovies(int len, int time) { int[][] movies = new int[len][2]; for (int i = 0; i < len; i++) { int a = (int) (Math.random() * time); int b = (int) (Math.random() * time); movies[i][0] = Math.min(a, b); movies[i][1] = Math.max(a, b); } return movies; } public static void main(String[] args) { int n = 10; int t = 20; int testTime = 10000; System.out.println("测试开始"); for (int i = 0; i < testTime; i++) { int len = (int) (Math.random() * n) + 1; int[][] movies = randomMovies(len, t); int ans1 = maxEnjoy1(movies); int ans2 = maxEnjoy2(movies); if (ans1 != ans2) { for (int[] m : movies) { System.out.println(m[0] + " , " + m[1]); } System.out.println(ans1); System.out.println(ans2); System.out.println("出错了"); } } System.out.println("测试结束"); } } 
