3439. 重新安排会议得到最多空余时间 I#

题目描述#

给定一个活动总时长 eventTime，以及 n 个非重叠会议 [startTime[i], endTime[i]]。

你可以重新安排至多 k 个会议（可在时间轴上平移，保持时长、相对顺序且不重叠），目的是最大化相邻两个会议（以及首尾边界）之间的最长连续空余时间。

示例 1：

1
输入：eventTime = 5, k = 1, startTime = [1,3], endTime = [2,5]
2
输出：2
3
解释：把会议 [1,2] 平移到 [2,3]，得到空余时间 [0,2]，长度为 2。

解法思路#

核心转化：把空余时间抽出来做成间隙数组，问题就变成定长滑窗求最大子数组和。

第一步，构建间隙数组 gaps。时间轴被会议切分成 n+1 段空余：

gaps[0] = startTime[0]（第 1 个会议前的空余）
gaps[i] = startTime[i] - endTime[i-1]（第 i 个会议与第 i-1 个之间的空余，1 ≤ i ≤ n-1）
gaps[n] = eventTime - endTime[n-1]（最后 1 个会议后的空余）

第二步，关键观察：既然会议可平移，那么把连续 k 个会议全部挪走，就可以把这 k 个会议两侧（含首尾）的 k+1 个间隙合并成一个大空余。

第三步，定长滑窗：问题等价于在 gaps 中找长度为 k+1 的连续子数组的最大和。用 入-更新-出 三步 O(1) 滑动更新窗口和 cur。

逐步举例（eventTime=5, k=1, start=[1,3], end=[2,5]）：

构建间隙：gaps[0]=1, gaps[1]=3-2=1, gaps[2]=5-5=0，即 gaps=[1,1,0]。
窗口大小 k+1 = 2：
- 窗口 [0,1]（gap 下标 0..1）和 = 1+1 = 2
- 窗口 [1,2] 和 = 1+0 = 1
最大和 = 2，对应把会议 [1,2] 挪走合并 gap[0]+gap[1]，与预期一致。

复杂度分析#

时间复杂度：O(n)，一次遍历。
空间复杂度：O(n)，用于存储间隙数组。

代码实现#

1
class Solution:
2
    def maxFreeTime(self, eventTime: int, k: int, startTime: list[int], endTime: list[int]) -> int:
3
        n = len(startTime)
4
        gaps = [0] * (n + 1)
5
        gaps[0] = startTime[0]
6
        for i in range(1, n):
7
            gaps[i] = startTime[i] - endTime[i - 1]
8
        gaps[n] = eventTime - endTime[-1]
9

10
        cur = sum(gaps[:k + 1])
11
        ans = cur
12
        for i in range(k + 1, n + 1):
13
            cur += gaps[i] - gaps[i - (k + 1)]
14
            if cur > ans:
15
                ans = cur
16

17
        return ans

1
import sys
2
import unittest
3
from pathlib import Path
4

5
sys.path.insert(0, str(Path(__file__).parent))
6
from solution import Solution
7

8

9
class TestMaxFreeTime(unittest.TestCase):
10
    def setUp(self):
11
        self.solution = Solution()
12

13
    def test_example1(self):
14
        self.assertEqual(self.solution.maxFreeTime(5, 1, [1, 3], [2, 5]), 2)
15

16
    def test_example2(self):
17
        self.assertEqual(self.solution.maxFreeTime(10, 1, [0, 2, 9], [1, 4, 10]), 6)
18

19
    def test_example3(self):
20
        self.assertEqual(self.solution.maxFreeTime(5, 2, [0, 1, 2, 3, 4], [1, 2, 3, 4, 5]), 0)
21

22
    def test_k_equals_n(self):
23
        self.assertEqual(self.solution.maxFreeTime(10, 3, [1, 3, 5], [2, 4, 6]), 7)
24

25
    def test_move_middle_meetings(self):
26
        self.assertEqual(self.solution.maxFreeTime(10, 2, [1, 3, 5], [2, 4, 6]), 6)
27

28
    def test_single_meeting(self):
29
        self.assertEqual(self.solution.maxFreeTime(10, 1, [2], [5]), 7)
30

31
    def test_no_gap(self):
32
        self.assertEqual(self.solution.maxFreeTime(5, 1, [0, 2], [2, 5]), 0)
33

34

35
if __name__ == "__main__":
36
    unittest.main()