Description
今天这道题和昨天类似,只是允许顺序变化。
Solution
把会议区间视作桌子,空余时间视作空位,我们要把一个桌子移到别的空位中。
初步想法是枚举桌子,找一个长度大于等于桌子长度的空位移过去。看上去,找一个长度最长的空位就好了。
但万一最长空位与桌子相邻呢?这并没有把桌子彻底移出去。
找次长的空位?万一最长空位和次长空位都与桌子相邻呢?
那就再找第三长的。不可能有三个空位都与同一个桌子相邻。
核心思路:计算长度最长的三个空位在哪,其中一定有一个空位不在移出去的桌子的左右两侧。如果空位长度大于等于桌子的长度,我们把桌子移到这个空位中。
设最大的三个空位所在的位置(下标)分别是 a,b,ca,b,ca,b,c。
枚举桌子,分类讨论:
- 如果桌子左右两侧的空位没有 aaa,那么把桌子移到 aaa。
- 否则,如果桌子左右两侧的空位没有 bbb,那么把桌子移到 bbb。
- 否则,把桌子移到 ccc。
继续分类讨论:
- 如果能移(有足够长的空位),新的空位长度 = 桌子长度 + 桌子左右两侧的空位长度。
- 如果不能移,那么只能移到左右相邻的桌子旁边,新的空位长度 = 桌子左右两侧的空位长度。
Code(C++、Python3)
可以复用昨天的代码。
C++
class Solution {
public:int maxFreeTime(int eventTime, vector<int>& startTime, vector<int>& endTime) {int n = startTime.size();auto get = [&](int i) -> int {if (i == 0) return startTime[0];if (i == n) return eventTime - endTime[n - 1];return startTime[i] - endTime[i - 1];};int a = 0, b = -1, c = -1;for (int i = 1; i <= n; i++) {int sz = get(i);if (sz > get(a)) c = b, b = a, a = i;else if (b < 0 || sz > get(b)) c = b, b = i;else if (c < 0 || sz > get(c)) c = i;}int ans = 0;for (int i = 0; i < n; i++) {int sz = endTime[i] - startTime[i];if (i != a && i + 1 != a && sz <= get(a) ||i != b && i + 1 != b && sz <= get(b) ||sz <= get(c)) ans = max(ans, get(i) + sz + get(i + 1));else ans = max(ans, get(i) + get(i + 1));}return ans;}
};
Python3
class Solution:def maxFreeTime(self, eventTime: int, startTime: List[int], endTime: List[int]) -> int:n = len(startTime)def get(i: int) -> int:if i == 0:return startTime[0]if i == n:return eventTime - endTime[n - 1]return startTime[i] - endTime[i - 1]a, b, c = 0, -1, -1for i in range(1, n + 1):sz = get(i)if sz > get(a):a, b, c = i, a, belif b < 0 or sz > get(b):b, c = i, belif c < 0 or sz > get(c):c = ians = 0for i, (s, e) in enumerate(zip(startTime, endTime)):sz = e - sif i != a and i + 1 != a and sz <= get(a) or \i != b and i + 1 != b and sz <= get(b) or \sz <= get(c):ans = max(ans, get(i) + sz + get(i + 1))else:ans = max(ans, get(i) + get(i + 1))return ans
欢迎大家关注LeetCode——C2h6oqwq。也恳求大家点赞收藏加关注~~~