3440.重新安排会议得到最多空余时间II

implementation, 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

解释：

活动中的所有时间都被会议安排满了。

提示：

1 <= eventTime <= 10^9
n == startTime.length == endTime.length
2 <= n <= 10^5
0 <= startTime[i] < endTime[i] <= eventTime
endTime[i] <= startTime[i + 1] 其中 i 在范围 [0, n - 2] 之间。

提示 1

If we reschedule a meeting earlier or later, we need to find a gap of length at least endTime[i] - startTime[i]. Try maintaining the gaps in some sorted data structure.

python

class Solution:
    def maxFreeTime(self, eventTime: int, startTime: list[int], endTime: list[int]) -> int:
        n = len(startTime)
        
        # 计算每个会议左侧可利用的最大空闲时间
        lRoom = [0] * n
        lRoom[0] = startTime[0]
        for i in range(1, n):
            lRoom[i] = max(lRoom[i - 1], startTime[i] - endTime[i - 1])
        
        # 计算每个会议右侧可利用的最大空闲时间
        rRoom = [0] * n
        rRoom[n - 1] = eventTime - endTime[n - 1]
        for i in range(n - 2, -1, -1):
            rRoom[i] = max(rRoom[i + 1], startTime[i + 1] - endTime[i])
        
        res = 0
        for i in range(n):
            # 左侧和右侧的时间点
            lTime = 0 if i == 0 else endTime[i - 1]
            rTime = eventTime if i == n - 1 else startTime[i + 1]
            
            # 当前会议的长度
            length = endTime[i] - startTime[i]
            
            # 更新最大空闲时间
            res = max(res, rTime - lTime - length)
            
            # 如果当前会议不是第一个会议，检查是否可以利用左侧的空闲时间
            if i > 0 and lRoom[i - 1] >= length:
                res = max(res, rTime - lTime)
            
            # 如果当前会议不是最后一个会议，检查是否可以利用右侧的空闲时间
            if i < n - 1 and rRoom[i + 1] >= length:
                res = max(res, rTime - lTime)
        
        return res

3440.重新安排会议得到最多空余时间II ​

3440.重新安排会议得到最多空余时间II