最大的观影时间问题

最大的观影时间问题

作者:Grey

原文地址:

博客园:最大的观影时间问题

CSDN:最大的观影时间问题

题目描述

一场电影开始和结束时间可以用一个小数组来表示["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 的时候,可以结算

image

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("测试结束");
    }
}

更多

算法和数据结构笔记