Description

今天這道題和昨天類似，只是允許順序變化。

Solution

把會議區間視作桌子，空余時間視作空位，我們要把一個桌子移到別的空位中。

初步想法是枚舉桌子，找一個長度大于等于桌子長度的空位移過去。看上去，找一個長度最長的空位就好了。

但萬一最長空位與桌子相鄰呢？這并沒有把桌子徹底移出去。

找次長的空位？萬一最長空位和次長空位都與桌子相鄰呢？

那就再找第三長的。不可能有三個空位都與同一個桌子相鄰。

核心思路：計算長度最長的三個空位在哪，其中一定有一個空位不在移出去的桌子的左右兩側。如果空位長度大于等于桌子的長度，我們把桌子移到這個空位中。

設最大的三個空位所在的位置（下標）分別是 $a,b,c$。

枚舉桌子，分類討論：

• 如果桌子左右兩側的空位沒有 $a$，那么把桌子移到 $a$。
• 否則，如果桌子左右兩側的空位沒有 $b$，那么把桌子移到 $b$。
• 否則，把桌子移到 $c$。

繼續分類討論：

• 如果能移（有足夠長的空位），新的空位長度 = 桌子長度 + 桌子左右兩側的空位長度。
• 如果不能移，那么只能移到左右相鄰的桌子旁邊，新的空位長度 = 桌子左右兩側的空位長度。

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。也懇求大家點贊收藏加關注~~~