2025-08-09：重新安排会议得到最多空余时间Ⅱ。用go语言，给出一个整数 eventTime，表示活动从 t=0 到 t=

福大大架构师每日一题

发布于 2025-08-13 14:15:23

17200

代码可运行

运行总次数：0

代码可运行

2025-08-09：重新安排会议得到最多空余时间Ⅱ。用go语言，给出一个整数 eventTime，表示活动从 t=0 到 t=eventTime 的时间区间。还有两个长度为 n 的数组 startTime 和 endTime，表示 n 个互不重叠的会议，第 i 个会议占据时间段 [startTime[i], endTime[i]]。

你可以最多对其中一个会议做平移操作（仅改变其起止时间位置，时长保持不变），并且移动后的会议必须仍然位于 [0, eventTime] 之内且与其它会议互不重叠。移动后各会议的先后顺序可以改变，也可以选择不移动任何会议。

目标是通过至多一次这样的平移，使时间轴上最长的不被任何会议占用的连续时段尽可能长。请输出在最佳移动方案下这一最长连续空闲时长。

1 <= eventTime <= 1000000000。

n == startTime.length == endTime.length。

2 <= n <= 100000。

0 <= startTime[i] < endTime[i] <= eventTime。

endTime[i] <= startTime[i + 1] 其中 i 在范围 [0, n - 2] 之间。

输入：eventTime = 5, startTime = [1,3], endTime = [2,5]。

输出：2。

解释：

将 [1, 2] 的会议安排到 [2, 3] ，得到空余时间 [0, 2] 。

题目来自力扣3440。

初始分析

1. 初始空闲时间：在不移动任何会议的情况下，最长空闲时间是所有相邻会议之间的间隔以及首尾的空闲时间的最大值。
- • 首部空闲：startTime[0] - 0
- • 相邻会议间隔：startTime[i] - endTime[i-1] 对所有 i
- • 尾部空闲：eventTime - endTime[n-1]
- • 初始最长空闲时间是这些值的最大值。
2. 移动一个会议的影响：移动一个会议可以尝试“填补”某些小的空闲时间，从而创造更大的空闲时间。
- • 移动会议 i 可以尝试将其放在某个位置，使得其前后的空闲时间合并。

解题步骤

1. 计算初始空闲时间：
- • 遍历所有会议，计算相邻会议之间的间隔以及首尾的空闲时间，记录最大值 max_gap。
2. 尝试移动每个会议：
- • 对于每个会议 i，尝试将其移除，然后计算移除后的空闲时间（即 startTime[i+1] - endTime[i-1]，假设 i 不是首尾会议）。
- • 然后尝试将会议 i 插入到其他位置，使得插入后的空闲时间最大化。
  - • 插入的位置可以是：
    - • 首部：startTime[i] = 0，endTime[i] = duration，检查是否与 startTime[0] 重叠。
    - • 尾部：endTime[i] = eventTime，startTime[i] = eventTime - duration，检查是否与 endTime[n-1] 重叠。
    - • 其他间隙：尝试将会议 i 插入到其他会议之间的间隙中，确保不重叠。
- • 对于每个可能的插入位置，计算新的空闲时间（即插入后相邻会议之间的间隔和首尾空闲时间），并更新 max_gap。
3. 优化移动策略：
- • 实际上，移动一个会议 i 的最优效果通常是将其“填补”到某个小的间隙中，从而合并两个相邻的空闲时间。
- • 因此，可以优先考虑移动那些持续时间较短的会议（因为更容易“填补”到小的间隙中）。
- • 对于会议 i，其持续时间为 duration = endTime[i] - startTime[i]。
- • 移除会议 i 后，其左右的空闲时间为 left_gap = startTime[i] - endTime[i-1] 和 right_gap = startTime[i+1] - endTime[i]（假设 i 不是首尾）。
- • 将会议 i 插入到其他位置后，原来的 left_gap + right_gap + duration 会成为新的空闲时间（因为移除了会议 i 的占用）。
- • 然后需要找到一个插入位置，使得插入后的空闲时间最大化。
4. 具体实现：
- • 首先计算初始的 max_gap。
- • 对于每个会议 i：
  - • 计算移除会议 i 后的空闲时间 removed_gap = startTime[i+1] - endTime[i-1]（假设 i 不是首尾）。
  - • 计算会议 i 的持续时间 duration = endTime[i] - startTime[i]。
  - • 尝试将会议 i 插入到其他间隙中：
    - • 插入到首部：如果 duration <= startTime[0]，则新的空闲时间为 startTime[0] - duration。
    - • 插入到尾部：如果 duration <= eventTime - endTime[n-1]，则新的空闲时间为 eventTime - endTime[n-1] - duration。
    - • 插入到其他间隙 j（即 startTime[j] - endTime[j-1] >= duration）：
      - • 新的空闲时间为 startTime[j] - endTime[j-1] - duration。
  - • 选择插入后能最大化 max(removed_gap, new_gap) 的位置。
- • 更新全局的 max_gap。

示例分析

以 eventTime = 5，startTime = [1, 3]，endTime = [2, 5] 为例：

1. 初始空闲时间：
- • 首部：1 - 0 = 1
- • 间隔：3 - 2 = 1
- • 尾部：5 - 5 = 0
- • max_gap = 1。
2. 尝试移动会议 0（[1, 2]）：
- • 移除后空闲时间：3 - 0 = 3。
- • 持续时间：1。
- • 尝试插入：
  - • 首部：[0, 1]，剩余空闲 3 - 1 = 2（因为 [0,1] 和 [3,5] 之间的空闲是 3 - 1 = 2）。
  - • 尾部：无法插入（5 - 5 = 0 < 1）。
  - • 其他间隙：无。
- • 新的 max_gap = max(3, 2) = 3（但实际空闲是 [0,1] 和 [1,3] 之间的 0，[3,5] 之间的 0，所以可能是 max(1, 2)）。
- • 更准确的计算：
  - • 插入到 [0,1] 后，会议为 [0,1] 和 [3,5]，空闲时间为 3 - 1 = 2 和 5 - 5 = 0，所以 max_gap = 2。
3. 尝试移动会议 1（[3,5]）：
- • 移除后空闲时间：5 - 2 = 3。
- • 持续时间：2。
- • 尝试插入：
  - • 首部：[0, 2]，剩余空闲 1 - 0 = 1（因为 [0,2] 和 [1,2] 重叠，不合法）。
  - • 尾部：无法插入（5 - 5 = 0 < 2）。
  - • 其他间隙：[1,2] 和 [3,5] 之间的间隙是 3 - 2 = 1 < 2，无法插入。
- • 无法移动会议 1。
4. 最终 max_gap = 2（通过移动会议 0 到 [0,1] 或 [2,3]）。

时间复杂度和空间复杂度

• 时间复杂度：
- • 计算初始 max_gap：O(n)。
- • 对于每个会议 i，尝试移动：
  - • 计算移除后的空闲时间：O(1)。
  - • 尝试插入到其他位置：需要检查所有间隙，最坏 O(n)。
- • 总时间复杂度：O(n^2)，但对于 n <= 1e5 来说不可行。
- • 优化：实际上可以预处理所有间隙，然后对于每个会议 i，尝试插入到最大的可用间隙中，可以优化到 O(n log n) 或 O(n)。
• 空间复杂度：
- • 额外空间用于存储间隙或其他中间变量：O(n)。

优化思路

• 预处理所有间隙（包括首尾），排序后可以快速找到最大的可用间隙。
• 对于每个会议 i，移除后可以尝试插入到最大的间隙中（只要 duration <= gap）。
• 这样可以将时间复杂度优化到 O(n log n)（排序间隙）或 O(n)（如果间隙已经有序）。

最终答案

对于给定的示例，输出 2。

Go完整代码如下：

package main

import (
    "fmt"
)

func maxFreeTime(eventTime int, startTime []int, endTime []int)int {
    n := len(startTime)
    q := make([]bool, n)
    t1, t2 := 0, 0
    for i := 0; i < n; i++ {
        if endTime[i]-startTime[i] <= t1 {
            q[i] = true
        }
        if i == 0 {
            t1 = max(t1, startTime[i])
        } else {
            t1 = max(t1, startTime[i]-endTime[i-1])
        }

        if endTime[n-i-1]-startTime[n-i-1] <= t2 {
            q[n-i-1] = true
        }
        if i == 0 {
            t2 = max(t2, eventTime-endTime[n-1])
        } else {
            t2 = max(t2, startTime[n-i]-endTime[n-i-1])
        }
    }

    res := 0
    for i := 0; i < n; i++ {
        left := 0
        if i != 0 {
            left = endTime[i-1]
        }
        right := eventTime
        if i != n-1 {
            right = startTime[i+1]
        }
        if q[i] {
            res = max(res, right-left)
        } else {
            res = max(res, right-left-(endTime[i]-startTime[i]))
        }
    }
    return res
}

func main() {
    eventTime := 5
    startTime := []int{1, 3}
    endTime := []int{2, 5}
    result := maxFreeTime(eventTime, startTime, endTime)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def max_free_time(eventTime: int, startTime: list, endTime: list) -> int:
    n = len(startTime)
    if n == 0:
        return eventTime

    q = [False] * n
    t1, t2 = 0, 0
    for i in range(n):
        if endTime[i] - startTime[i] <= t1:
            q[i] = True
        if i == 0:
            t1 = max(t1, startTime[i])
        else:
            t1 = max(t1, startTime[i] - endTime[i-1])

        j = n - i - 1
        if endTime[j] - startTime[j] <= t2:
            q[j] = True
        if i == 0:
            t2 = max(t2, eventTime - endTime[n-1])
        else:
            # 对应 Go 中的 startTime[n-i] - endTime[n-i-1]
            t2 = max(t2, startTime[n - i] - endTime[n - i - 1])

    res = 0
    for i in range(n):
        left = 0if i == 0else endTime[i-1]
        right = eventTime if i == n-1else startTime[i+1]
        if q[i]:
            res = max(res, right - left)
        else:
            res = max(res, right - left - (endTime[i] - startTime[i]))
    return res

if __name__ == "__main__":
    eventTime = 5
    startTime = [1, 3]
    endTime = [2, 5]
    result = max_free_time(eventTime, startTime, endTime)
    print(result)