What is the core pattern in Reschedule Meetings for Maximum Free Time II?

The core pattern is a greedy choice plus invariant validation, focusing on rescheduling one meeting to maximize continuous free time.

Can multiple meetings be rescheduled?

No, the problem limits rescheduling to at most one meeting while maintaining all non-overlapping constraints.

How do I compute maximum free time efficiently?

Track gaps between meetings and evaluate each meeting's potential shift using a greedy approach to maximize the largest gap.

Do I need to sort meetings first?

Yes, sorting by startTime ensures gap calculations and rescheduling validations are efficient and correct.

What common mistake should I avoid?

A common error is ignoring edge intervals or violating the non-overlapping constraint when moving a meeting.

#3440

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

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

给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间没有重叠的会议，其中第 i 个会议的时间为 [startTim…

数组贪心枚举

题目描述

给你一个整数 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⁹
n == startTime.length == endTime.length
2 <= n <= 10⁵
0 <= startTime[i] < endTime[i] <= eventTime
endTime[i] <= startTime[i + 1] 其中 i 在范围 [0, n - 2] 之间。

lightbulb

解题思路

方法一：贪心

根据题目描述，对于会议 $i$ ，我们记它左侧非空闲位置为 $l_i$ ，右侧非空闲位置为 $r_i$ ，记会议 $i$ 的时长为 $w_i = \text{endTime}[i] - \text{startTime}[i]$ ，则：

l_i = \begin{cases} 0 & i = 0 \\\\ \text{endTime}[i - 1] & i \gt 0 \end{cases}

r_i = \begin{cases} \text{eventTime} & i = n - 1 \\\\ \text{startTime}[i + 1] & i \lt n - 1 \end{cases}

那么它可以向左移动，也可以向右移动，此时空闲时间为：

r_i - l_i - w_i

如果左侧存在最大的空闲时间 $\text{pre}_{i - 1}$ ，满足 $\text{pre}_{i - 1} \geq w_i$ ，则可以将会议 $i$ 向左移动到该位置，得到新的空闲时间：

r_i - l_i

同理，如果右侧存在最大的空闲时间 $\text{suf}_{i + 1}$ ，满足 $\text{suf}_{i + 1} \geq w_i$ ，则可以将会议 $i$ 向右移动到该位置，得到新的空闲时间：

r_i - l_i

因此，我们首先预处理两个数组 $\text{pre}$ 和 $\text{suf}$ ，其中 $\text{pre}[i]$ 表示 $[0, i]$ 范围内的最大空闲时间， $\text{suf}[i]$ 表示 $[i, n - 1]$ 范围内的最大空闲时间。然后遍历每个会议 $i$ ，计算它移动后的最大空闲时间，取最大值即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为会议的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

class Solution:
    def maxFreeTime(
        self, eventTime: int, startTime: List[int], endTime: List[int]
    ) -> int:
        n = len(startTime)
        pre = [0] * n
        suf = [0] * n
        pre[0] = startTime[0]
        suf[n - 1] = eventTime - endTime[-1]
        for i in range(1, n):
            pre[i] = max(pre[i - 1], startTime[i] - endTime[i - 1])
        for i in range(n - 2, -1, -1):
            suf[i] = max(suf[i + 1], startTime[i + 1] - endTime[i])
        ans = 0
        for i in range(n):
            l = 0 if i == 0 else endTime[i - 1]
            r = eventTime if i == n - 1 else startTime[i + 1]
            w = endTime[i] - startTime[i]
            ans = max(ans, r - l - w)
            if i and pre[i - 1] >= w:
                ans = max(ans, r - l)
            elif i + 1 < n and suf[i + 1] >= w:
                ans = max(ans, r - l)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) as each meeting is evaluated once for potential rescheduling. Space complexity is O(1) if only tracking current maximum gaps without additional arrays.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Checking if the candidate meeting can extend the largest gap indicates awareness of greedy optimization.
question_mark
Confirming non-overlapping constraints after rescheduling shows understanding of invariant maintenance.
question_mark
Evaluating all possible single reschedules signals thorough exploration of array-based solutions.

warning

常见陷阱

外企场景

error
Forgetting to maintain the duration of the rescheduled meeting, which can invalidate gaps.
error
Overlooking edge gaps at the start or end of the event when computing maximum free time.
error
Assuming multiple meetings can be moved instead of only one, violating problem constraints.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow rescheduling multiple meetings to maximize free time using a dynamic greedy approach.
arrow_right_alt
Determine minimum total idle time instead of maximum free interval with a similar rescheduling strategy.
arrow_right_alt
Consider meetings with flexible durations, adjusting both start and end times under non-overlap constraints.

help

常见问题

外企场景

继续练习

#3434 子数组操作后的最大频率 #3588 找到最大三角形面积 #3630 划分数组得到最大异或运算和与运算之和