Medium

题目描述

给定一个整数 eventTime，表示事件的持续时间。还给定两个长度为 n 的整数数组 startTime 和 endTime。

这些数组表示在事件期间（时间 t = 0 到 t = eventTime）发生的 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] 内。

解题思路

设 gaps[0] 为第一个会议前的空闲时间，gaps[n] 为最后一个会议后的空闲时间，其余 gaps[i] 表示相邻会议之间的空闲时间。

枚举移动第 i 个会议，持续时间记为 duration：

  1. 移除会议后，gaps[i]、会议本身和 gaps[i + 1] 会连成一段。
  2. 如果某个不相邻间隙能够容纳该会议，就可以把会议移到那里，原位置完整释放，候选答案为 gaps[i] + duration + gaps[i + 1]。
  3. 否则会议仍需放回原来的合并区间，候选答案为 gaps[i] + gaps[i + 1]。

用前缀最大值和后缀最大值即可在 O(1) 时间查询除 gaps[i]、gaps[i + 1] 外的最大间隙，因此总时间复杂度为 O(n)。

代码实现

class Solution {
public:
    int maxFreeTime(int eventTime, vector<int>& startTime, vector<int>& endTime) {
        int n = startTime.size();
        vector<int> gaps(n + 1);
        gaps[0] = startTime[0];
        for (int i = 1; i < n; i++) {
            gaps[i] = startTime[i] - endTime[i - 1];
        }
        gaps[n] = eventTime - endTime[n - 1];

        vector<int> prefix(n + 1), suffix(n + 1);
        prefix[0] = gaps[0];
        for (int i = 1; i <= n; i++) {
            prefix[i] = max(prefix[i - 1], gaps[i]);
        }
        suffix[n] = gaps[n];
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = max(suffix[i + 1], gaps[i]);
        }

        int answer = prefix[n];
        for (int i = 0; i < n; i++) {
            int duration = endTime[i] - startTime[i];

            int outsideMax = 0;
            if (i > 0) outsideMax = max(outsideMax, prefix[i - 1]);
            if (i + 2 <= n) outsideMax = max(outsideMax, suffix[i + 2]);

            int candidate = gaps[i] + gaps[i + 1];
            if (outsideMax >= duration) candidate += duration;
            answer = max(answer, candidate);
        }

        return answer;
    }
};

class Solution:
    def maxFreeTime(self, eventTime: int, startTime: List[int], endTime: List[int]) -> int:
        n = len(startTime)
        gaps = [0] * (n + 1)
        gaps[0] = startTime[0]
        for i in range(1, n):
            gaps[i] = startTime[i] - endTime[i - 1]
        gaps[n] = eventTime - endTime[n - 1]

        prefix = [0] * (n + 1)
        suffix = [0] * (n + 1)
        prefix[0] = gaps[0]
        for i in range(1, n + 1):
            prefix[i] = max(prefix[i - 1], gaps[i])
        suffix[n] = gaps[n]
        for i in range(n - 1, -1, -1):
            suffix[i] = max(suffix[i + 1], gaps[i])

        answer = prefix[n]
        for i in range(n):
            duration = endTime[i] - startTime[i]

            outside_max = 0
            if i > 0:
                outside_max = max(outside_max, prefix[i - 1])
            if i + 2 <= n:
                outside_max = max(outside_max, suffix[i + 2])

            candidate = gaps[i] + gaps[i + 1]
            if outside_max >= duration:
                candidate += duration
            answer = max(answer, candidate)

        return answer

public class Solution {
    public int MaxFreeTime(int eventTime, int[] startTime, int[] endTime) {
        int n = startTime.Length;
        int[] gaps = new int[n + 1];
        gaps[0] = startTime[0];
        for (int i = 1; i < n; i++) {
            gaps[i] = startTime[i] - endTime[i - 1];
        }
        gaps[n] = eventTime - endTime[n - 1];

        int[] prefix = new int[n + 1];
        int[] suffix = new int[n + 1];
        prefix[0] = gaps[0];
        for (int i = 1; i <= n; i++) {
            prefix[i] = Math.Max(prefix[i - 1], gaps[i]);
        }
        suffix[n] = gaps[n];
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = Math.Max(suffix[i + 1], gaps[i]);
        }

        int answer = prefix[n];
        for (int i = 0; i < n; i++) {
            int duration = endTime[i] - startTime[i];

            int outsideMax = 0;
            if (i > 0) outsideMax = Math.Max(outsideMax, prefix[i - 1]);
            if (i + 2 <= n) outsideMax = Math.Max(outsideMax, suffix[i + 2]);

            int candidate = gaps[i] + gaps[i + 1];
            if (outsideMax >= duration) candidate += duration;
            answer = Math.Max(answer, candidate);
        }

        return answer;
    }
}

var maxFreeTime = function(eventTime, startTime, endTime) {
    const n = startTime.length;
    const gaps = new Array(n + 1).fill(0);
    gaps[0] = startTime[0];
    for (let i = 1; i < n; i++) {
        gaps[i] = startTime[i] - endTime[i - 1];
    }
    gaps[n] = eventTime - endTime[n - 1];

    const prefix = new Array(n + 1).fill(0);
    const suffix = new Array(n + 1).fill(0);
    prefix[0] = gaps[0];
    for (let i = 1; i <= n; i++) {
        prefix[i] = Math.max(prefix[i - 1], gaps[i]);
    }
    suffix[n] = gaps[n];
    for (let i = n - 1; i >= 0; i--) {
        suffix[i] = Math.max(suffix[i + 1], gaps[i]);
    }

    let answer = prefix[n];
    for (let i = 0; i < n; i++) {
        const duration = endTime[i] - startTime[i];

        let outsideMax = 0;
        if (i > 0) outsideMax = Math.max(outsideMax, prefix[i - 1]);
        if (i + 2 <= n) outsideMax = Math.max(outsideMax, suffix[i + 2]);

        let candidate = gaps[i] + gaps[i + 1];
        if (outsideMax >= duration) candidate += duration;
        answer = Math.max(answer, candidate);
    }

    return answer;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(n)

其中 n 是会议数量。间隙、前缀最大值和后缀最大值各遍历一次，枚举每个会议时只做 O(1) 查询。