LeetCode中國站原文

https://leetcode.cn/problems/reschedule-meetings-for-maximum-free-time-ii/

原始題目

題目描述

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

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

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

請你返回重新安排會議以后，可以得到的 最大 空余時間。

注意，會議 不能 安排到整個活動的時間以外，且會議之間需要保持互不重疊。

注意：重新安排會議以后，會議之間的順序可以發生改變。

示例1：

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

示例2：

輸入：eventTime = 10, startTime = [0,7,9], endTime = [1,8,10]
輸出：7
解釋：將 [0, 1] 的會議安排到 [8, 9] ，得到空余時間 [0, 7] 。

示例3：

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

示例4：

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

講解

如果你看過我們之前對 I 系列的討論（【LeetCode 3439. 重新安排會議得到最多空余時間 I】解析），你會發現這道題有一個關鍵性的變化：會議的相對順序可以改變了！ 這個變化讓上一題精妙的“滑動窗口”解法瞬間失效，迫使我們必須尋找新的出路。

這篇文章將帶你從零開始，理清思路，看穿問題的本質，并最終理解一個堪稱“神仙”級別的解法。

1. 新規則，新挑戰

我們先來回顧一下規則：

• 能力：可以平移最多 1 個會議。
• 變化：平移后，會議的順序可以任意改變。
• 目標：創造出一個盡可能長的連續空閑時間。

“順序可以改變”是這道題的“游戲規則改變者”。這意味著，我們可以從所有會議中，任意挑選一個“倒霉蛋”會議，把它塞進任意一個能容納它的空隙里。

那么，我們的決策過程就變成了：

1. 選哪個會議去移動？
2. 把它移動到哪里去？

我們的目標是讓這兩個決策的組合，能產生最大的收益。

2. 收益從何而來？兩種可能性的誕生

要獲得最長的空閑時間，最終的結果只可能從兩種情況中產生：

情況一：不移動任何會議

如果我們選擇不動，那么最長的空閑時間就是所有原始“空隙”中，最長的那一個。這是我們的保底收益。

情況二：移動 1 個會議

這是問題的精髓所在。當我們決定移動一個會議，比如「會議i」，會發生什么？

• 「會議i」原本占用的空間 [startTime[i], endTime[i]] 被釋放了。
• 這個被釋放的空間，會和它前后的空隙（「空隙i」和「空隙i+1」）合并，形成一個巨大的新空隙！

這個新產生的巨大空隙，其長度為 startTime[i+1] - endTime[i-1]。

但是，這個美好的情況有一個前提條件：被我們移動的「會議i」必須有地方可去！也就是說，它的時長 (endTime[i] - startTime[i]) 必須小于或等于我們場上存在的某一個原始空隙的長度。

3. 我們的終極策略

結合以上分析，一個清晰的，雖然可能比較慢的策略誕生了：

1. 預處理：

   • 計算出所有會議各自的時長。
   • 計算出所有原始空隙的長度，并找到其中的最大值 max_original_gap。

2. 遍歷與決策：

   • 遍歷每一個會議 i (從 0 到 n-1)，假裝要移動它。
   • 計算收益：如果移動會議 i，能創造出的新空隙長度為 startTime[i+1] - endTime[i-1]。
   • 檢查條件：會議 i 的時長，是否 <= max_original_gap？
     • 如果條件滿足：說明移動是可行的。我們就在這個“收益”和我們已知的“最大收益”之間取一個更大的。
     • 如果條件不滿足：說明會議 i 太長了，根本沒地方放。我們無法移動它，只能放棄這個方案。

3. 綜合比較：最后，別忘了把“移動會議”能產生的最大收益，和“不移動會議”（即 max_original_gap）本身再比較一次，取最終的勝利者。

這個 O(N) 的預處理 + O(N) 的遍歷決策，總時間復雜度為 O(N)，空間復雜度也是 O(N)。這是一個非常可靠且正確的解法。

4. 當策略被壓縮到極致

現在，讓我們來欣賞一下那段極其精煉的、只用兩個 for 循環就解決問題的代碼。它沒有顯式地預處理和存儲，而是將所有計算都“動態地”揉進了循環里。

這個解法的核心思想是：通過一次從左到右和一次從右到左的遍歷，來模擬“向前看”和“向后看”，從而解決移動條件檢查的問題。

第一次遍歷：從左到右（向左看）

這次遍歷，當我們站在會議 i 的位置時，我們只知道在它左邊發生的所有事。

// mx 在這里代表“截至目前，我左邊見過的最大空隙是多少”
int mx = 0;
for (int i = 0; i < n; i++) {int len = endTime[i] - startTime[i]; // 會議i的時長// 檢查移動條件：會議i能放進左邊的最大空隙嗎？if (len <= mx) {// 如果可以，就計算移動它能產生的收益，并更新全局最大值 resint potential_gap = (i == n-1 ? eventTime : startTime[i+1]) - (i == 0 ? 0 : endTime[i-1]);res = Math.max(res, potential_gap);}// 更新狀態，為下一次循環做準備// 1. 讓 mx 知道剛剛路過的這個空隙int current_gap = startTime[i] - (i == 0 ? 0 : endTime[i-1]);mx = Math.max(mx, current_gap);// 2. 同時，我們也要考慮不移動的情況，即原始空隙本身也是備選答案res = Math.max(res, current_gap);
}

注意：為了便于理解，我稍微修改了代碼邏輯，使其更符合直覺。官方題解的寫法更為精煉，但核心思想一致。

這次遍歷的盲點在于，它不知道會議 i 右邊是否有一個超級大的空隙可以容納它。

第二次遍歷：從右到左（向右看）

為了彌補這個盲點，我們需要一次完全對稱的、從右到左的遍歷。

// mx 重置，代表“截至目前，我右邊見過的最大空隙是多少”
mx = 0; 
for (int i = n - 1; i >= 0; i--) {int len = endTime[i] - startTime[i];// 檢查移動條件：會議i能放進右邊的最大空隙嗎？if (len <= mx) {int potential_gap = (i == n-1 ? eventTime : startTime[i+1]) - (i == 0 ? 0 : endTime[i-1]);res = Math.max(res, potential_gap);}// 更新狀態int current_gap = (i == n-1 ? eventTime : startTime[i+1]) - endTime[i];mx = Math.max(mx, current_gap);res = Math.max(res, current_gap);
}```### 最終代碼呈現將上述思想融合，并采用官方題解的精煉寫法，就得到了最終的答案：```java
class Solution {public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) {int n = startTime.length;int res = 0;// 第一次遍歷：從左到右int mx_left_gap = 0; // 記錄左側的最大空隙int last_end = 0;for (int i = 0; i < n; i++) {int len = endTime[i] - startTime[i];int potential_new_gap = (i == n - 1 ? eventTime : startTime[i + 1]) - last_end;if (len <= mx_left_gap) {res = Math.max(res, potential_new_gap);} else {// 如果不能移動，我們能獲得的最大空隙，// 就是把當前會議的時長從 potential_new_gap 中挖掉res = Math.max(res, potential_new_gap - len);}mx_left_gap = Math.max(mx_left_gap, startTime[i] - last_end);last_end = endTime[i];}// 第二次遍歷：從右到左int mx_right_gap = 0; // 記錄右側的最大空隙int last_start = eventTime;for (int i = n - 1; i >= 0; i--) {int len = endTime[i] - startTime[i];int potential_new_gap = last_start - (i == 0 ? 0 : endTime[i - 1]);if (len <= mx_right_gap) {res = Math.max(res, potential_new_gap);} else {res = Math.max(res, potential_new_gap - len);}mx_right_gap = Math.max(mx_right_gap, last_start - startTime[i]);last_start = startTime[i];}return res;}
}

等價的但是我自己嘗試的代碼

由于本人的算法知識并不算非常強，在一開始寫左右分別看的代碼出現了很多問題，這里給出一個可能冗余但是能看懂邏輯的相同的“向左看”+向右看的代碼

class Solution {// time = O(n), space = O(n)public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) {// 當前會議的長度，從startTime或者endTime任意一個數組的長度取值都可以。int meetingCount = startTime.length;// 記錄最終的答案int ans = 0;// 臨時的最大值int tempMaxGap = 0;// 接下來要從左向右看。// 記錄下來走過來最長的路int maxGap = 0;for(int i=0; i< meetingCount; i++){// 是否是第一個會議boolean isFirstMeeting = i==0;// 是否是最后一個會議boolean isLastMeeting = i == meetingCount - 1;// 左邊的空隙int leftGap = isFirstMeeting ? startTime[0] : startTime[i] - endTime[i-1];// 本次循環中會議的持續時間int meetingDuration = endTime[i] - startTime[i];if(maxGap >= meetingDuration){// 如果當前會議的時長比走過的最大間隔還要大，或者等于最大時長，代表可以插入// 上一個會議的結束點int lastMeetingEnd = isFirstMeeting ? 0 : endTime[i-1];// 下一個會議的開始時間int nextMeetingStart = isLastMeeting ? eventTime : startTime[i+1];// 新的巨大空隙tempMaxGap = nextMeetingStart - lastMeetingEnd;}else{// 右邊的空隙int rightGap = isLastMeeting ? eventTime - endTime[i]: startTime[i+1] - endTime[i];// 新的空隙(為左邊的空隙+右邊的空隙)tempMaxGap = leftGap + rightGap;}ans = Math.max(ans, tempMaxGap);// 更新記憶maxGap = Math.max(maxGap, leftGap);}// 更新ansans = Math.max(ans, maxGap);// 重置記憶maxGapmaxGap = 0;for(int i=meetingCount - 1; i>=0; i--){// 是否是第一個會議boolean isFirstMeeting = i==0;// 是否是最后一個會議boolean isLastMeeting = i == meetingCount - 1;// 右邊的空隙int rightGap = isLastMeeting ? eventTime - endTime[i]: startTime[i+1] - endTime[i];// 本次循環中會議的持續時間int meetingDuration = endTime[i] - startTime[i];if(maxGap >= meetingDuration){// 如果當前會議的時長比走過的最大間隔還要大，或者等于最大時長，代表可以插入// 上一個會議的結束點int lastMeetingEnd = isFirstMeeting ? 0 : endTime[i-1];// 下一個會議的開始時間int nextMeetingStart = isLastMeeting ? eventTime : startTime[i+1];// 新的巨大空隙tempMaxGap = nextMeetingStart - lastMeetingEnd;}else{// 左邊的空隙int leftGap = isFirstMeeting ? startTime[0] : startTime[i] - endTime[i-1];// 新的空隙(為左邊的空隙+右邊的空隙)tempMaxGap = leftGap + rightGap;}ans = Math.max(ans, tempMaxGap);// 更新記憶maxGap = Math.max(maxGap, rightGap );}return ans;}
}

5. 結論

這道題是對問題分析和抽象能力的絕佳考驗。它告訴我們：

1. 明確規則變化：”相對順序可變“是解題的鑰匙。
2. 分解問題：將復雜問題分解為“移動”和“不移動”兩種獨立的、可分析的情況。
3. 優化實現：思考如何用更少的空間和時間復雜度來實現策略。兩次遍歷的解法正是這種極致優化的產物。