LeetCode 3439. 重新安排會議得到最多空餘時間 I（滑動視窗圖解）

3439. 重新安排會議得到最多空餘時間 I

題目描述

給你一個整數 eventTime 表示一個活動的總時長，這個活動開始於 t = 0，結束於 t = eventTime。

同時給你兩個長度為 n 的整數陣列 startTime 和 endTime。它們表示這次活動中 n 個時間沒有重疊的會議，其中第 i 個會議的時間為 [startTime[i], endTime[i]]。

你可以重新安排至多 k 個會議，安排的規則是將會議時間平移，且保持原來的會議時長，你的目的是移動會議後最大化相鄰兩個會議之間的最長連續空餘時間。

移動前後所有會議之間的相對順序需要保持不變，而且會議時間也需要保持互不重疊。

請你回傳重新安排會議以後，可以得到的最大空餘時間。

注意，會議不能安排到整個活動的時間以外。

範例 1

輸入：eventTime = 5, k = 1, startTime = [1,3], endTime = [2,5]
輸出：2
解釋：將 [1, 2] 的會議安排到 [2, 3]，得到空餘時間 [0, 2]。

範例 2

輸入：eventTime = 10, k = 1, startTime = [0,2,9], endTime = [1,4,10]
輸出：6
解釋：將 [2, 4] 的會議安排到 [1, 3]，得到空餘時間 [3, 9]。

範例 3

輸入：eventTime = 5, k = 2, startTime = [0,1,2,3,4], endTime = [1,2,3,4,5]
輸出：0
解釋：活動中的所有時間都被會議安排滿了。

限制

• 1 <= eventTime <= 10^9
• n == startTime.length == endTime.length
• 2 <= n <= 10^5
• 1 <= k <= n
• 0 <= startTime[i] < endTime[i] <= eventTime
• endTime[i] <= startTime[i + 1]，其中 i 在範圍 [0, n - 2] 之間。

本文題解思路與程式碼整理自 LeetCode 題解作者「灵茶山艾府」，題解連結。圖解與步驟說明為自行補充。

前置知識：定長滑動視窗

定長視窗每次右移一格，少一個最左元素、多一個新元素，所以視窗和可以用 s += 新 - 舊 在 O(1) 內更新，不必每次重算。前面幾篇已經用過，例如 2841 和 1423。

思路

這題不太好直接看出是滑動視窗，要分三步轉換。

第一步：把會議時間軸看成「會議」和「空餘時間」交錯

整個活動是一條 0 ~ eventTime 的時間軸，會議把它切成一段一段。下面用範例 2（eventTime = 10），深色是會議、淺色是空餘時間。按「下一步」看每個空餘時間段是怎麼算出來的：

上一步 下一步 重置

eventTime = 10，startTime = [0,2,9]，endTime = [1,4,10]：深色是會議，淺色是空餘時間

依序算出每個空餘時間段，存進 free 陣列

重點整理：

• 有 n 個會議，就有 n + 1 個空餘時間段：最左邊一個、最右邊一個，中間有 n − 1 個夾在兩個相鄰會議之間。
• 空餘時間段的長度可以是 0（例如會議剛好接在一起，或第一個會議從 0 開始）。
• 三種長度的算法：
  • 最左邊：startTime[0]
  • 中間：startTime[i] - endTime[i - 1]
  • 最右邊：eventTime - endTime[n - 1]
• 範例 1 的空餘時間段是 [1, 1, 0]，範例 2 是 [0, 1, 5, 0]，範例 3 是 [0, 0, 0, 0, 0, 0]。

第二步：移動會議，其實是在「合併」相鄰的空餘時間段

看範例 1（eventTime = 5，會議 [1,2] 和 [3,5]，空餘時間段是 [0,1]、[2,3]、[]）：

• 把會議 [1, 2] 向左移到 [0, 1]，左邊的空餘時間段 [0, 1] 消失，右邊多出 [1, 3]，長度變成 1 + 1 = 2。
• 把會議 [1, 2] 向右移到 [2, 3]，右邊的空餘時間段 [2, 3] 消失，左邊變成 [0, 2]，長度同樣是 1 + 1 = 2。

不管往哪邊移，都等於把這個會議兩側長為 1 的兩段空餘時間合併成一段。移動會議不會讓空餘時間的總量改變，只是把它們湊在一起。

推廣到 k 個會議：

• k = 1：移動一個會議，合併它兩側相鄰的 2 個空餘時間段。
• k = 2：移動兩個會議。因為會議的相對順序不能變，會議也不能互相穿過，要讓空餘時間湊成一大段，最好移動相鄰的兩個會議，把它們夾著的 3 個連續空餘時間段全部合併。如果移動的兩個會議不相鄰，湊出來的只是兩個分開的小段，不會比合併 3 個連續段更長。
• 一般地，最優做法是合併連續 k + 1 個空餘時間段。

下面用範例 2 實際看看。可以切換 k，再逐個視窗往右看：上排是原本的時間軸，藍框是視窗內的 k + 1 個空餘時間段和它們夾著的 k 個會議；下排是把這 k 個會議擠到一側後的樣子，綠色就是合併出來的連續空餘時間。

最多移動 k 個會議：k = 0k = 1k = 2k = 3

上一個視窗 下一個視窗 重置

原本（藍框是視窗內連續 k + 1 個空餘時間段，以及它們夾著的 k 個會議）

把視窗內的 k 個會議擠到一側之後（綠色是合併出來的連續空餘時間）

這個視窗合併出的空餘時間 s0

目前最大值 ans0

可以自己玩玩看：

• k = 0：不能移動任何會議，答案就是原本最長的單一空餘時間段（5）。
• k = 1：視窗長度 2，三個視窗的和依序是 0+1 = 1、1+5 = 6、5+0 = 5，最大是 6，就是範例 2 的答案。
• k = 3：視窗長度 4，剛好涵蓋所有空餘時間段，等於把全部會議擠到一側，得到 eventTime 減去所有會議時長。

第三步：轉成定長滑動視窗

問題於是變成：

給你 n + 1 個空餘時間段的長度，合併其中連續 k + 1 個，得到的最大長度是多少？

也就是：長度為 k + 1 的視窗，求最大視窗和，這是標準的定長滑動視窗。

視窗模板（和前面幾篇一樣）：

1. 入：新元素進入視窗，s += free[i]。
2. 若視窗還沒滿（i < k），繼續。注意視窗長度是 k + 1，所以 i = 0 ~ k - 1 時還不滿；到 i = k 視窗才剛好有 k + 1 個。
3. 更新：用 s 更新答案的最大值。
4. 出：最左邊的 free[i - k] 離開視窗，s -= free[i - k]。

兩種寫法的差別只在「空餘時間段的長度」怎麼取得：

• 寫法一：先建一個長為 n + 1 的 free 陣列存起來。
• 寫法二：用一個函式 get(i) 即時計算，省掉陣列，空間 O(1)。

方法一：建 free 陣列

思路

1. 建立長為 n + 1 的陣列 free，依第一步的三種規則填入各空餘時間段的長度。
2. 套定長滑窗模板，視窗長 k + 1：i 往右走，先 s += free[i]；若 i < k，視窗還沒滿，繼續；否則用 s 更新 ans，再 s -= free[i - k]。

圖解（可互動）

用範例 2：free = [0,1,5,0]，k = 1，視窗長度 2。視窗和依序是 1、6、5，ans 會從 0 → 1 → 6 → 6。

上一步 下一步 重置

eventTime = 10，k = 1，startTime = [0,2,9]，endTime = [1,4,10]（空餘時間段共 n + 1 = 4 個，視窗長度 k + 1 = 2）

視窗（k + 1 個空餘時間段） 入 = 新進入 出 = 更新後離開

視窗總和 s0

目前最大值 ans0

把這個過程寫成表格（k = 1）：

i	free[i]	入：s += free[i]	視窗滿了嗎	更新：ans	出：s -= free[i-k]
0	0	s = 0	否（i < k），跳過	不更新	不減
1	1	s = 0 + 1 = 1	是	max(0, 1) = 1	s = 1 - free[0] = 1
2	5	s = 1 + 5 = 6	是	max(1, 6) = 6	s = 6 - free[1] = 5
3	0	s = 5 + 0 = 5	是	max(6, 5) = 6	s = 5 - free[2] = 0

最後 ans = 6。

解法（灵茶山艾府）

class Solution {
    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        int n = startTime.length;
        int[] free = new int[n + 1];
        free[0] = startTime[0]; // 最左邊的空餘時間段
        for (int i = 1; i < n; i++) {
            free[i] = startTime[i] - endTime[i - 1]; // 中間的空餘時間段
        }
        free[n] = eventTime - endTime[n - 1]; // 最右邊的空餘時間段

        // 套定長滑窗模板（視窗長為 k+1）
        int ans = 0;
        int s = 0;
        for (int i = 0; i <= n; i++) {
            s += free[i];
            if (i < k) {
                continue;
            }
            ans = Math.max(ans, s);
            s -= free[i - k];
        }
        return ans;
    }
}

複雜度分析

• 時間複雜度：O(n)，其中 n 是 startTime 的長度。
• 空間複雜度：O(n)。

方法二：空間優化（用函式取代陣列）

思路

流程和方法一完全相同，只是把「第 i 個空餘時間段的長度」包成函式 get(i)：進入視窗時算一次 get(i)，離開視窗時再算一次 get(i - k)。每個值多算一次，換來不用 free 陣列，空間降為 O(1)。

get(i) 對應第一步的三種情況：i == 0 是最左邊、i == n 是最右邊，其餘是中間。

圖解（可互動）

同樣用範例 2。看資訊區：這裡不會有 free 陣列，每一步都是直接由 startTime、endTime 算出該空餘時間段。

上一步 下一步 重置

eventTime = 10，k = 1，startTime = [0,2,9]，endTime = [1,4,10]（空餘時間段共 n + 1 = 4 個，視窗長度 k + 1 = 2）

視窗（k + 1 個空餘時間段） 入 = 新進入 出 = 更新後離開

視窗總和 s0

目前最大值 ans0

解法（灵茶山艾府）

class Solution {
    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        int ans = 0;
        int s = 0;
        for (int i = 0; i <= startTime.length; i++) {
            s += get(i, eventTime, startTime, endTime);
            if (i < k) {
                continue;
            }
            ans = Math.max(ans, s);
            s -= get(i - k, eventTime, startTime, endTime);
        }
        return ans;
    }

    private int get(int i, int eventTime, int[] startTime, int[] endTime) {
        if (i == 0) {
            return startTime[0]; // 最左邊的空餘時間段
        }
        int n = startTime.length;
        if (i == n) {
            return eventTime - endTime[n - 1]; // 最右邊的空餘時間段
        }
        return startTime[i] - endTime[i - 1]; // 中間的空餘時間段
    }
}

複雜度分析

• 時間複雜度：O(n)，其中 n 是 startTime 的長度。
• 空間複雜度：O(1)。