最大的觀影時間問題

作者：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 的時候，可以結算

當 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("測試結束");
    }
}

更多

演演算法和資料結構筆記