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. 优化实现：思考如何用更少的空间和时间复杂度来实现策略。两次遍历的解法正是这种极致优化的产物。