Medium

题目描述

给定一个整数 eventTime 表示事件的持续时间，事件从时间 t = 0 持续到时间 t = eventTime。

还给定两个长度为 n 的整数数组 startTime 和 endTime，表示 n 个不重叠会议的开始和结束时间，其中第 i 个会议在时间 [startTime[i], endTime[i]] 期间进行。

你可以通过移动开始时间来重新安排最多 k 个会议，同时保持相同的持续时间，以最大化事件期间最长的连续空闲时间。

所有会议的相对顺序应保持不变，并且它们应保持不重叠。

返回重新安排会议后可能的最大空闲时间。

注意会议不能重新安排到事件时间之外。

示例 1：

输入：eventTime = 5, k = 1, startTime = [1,3], endTime = [2,5]
输出：2
解释：将会议 [1, 2] 重新安排到 [2, 3]，在时间 [0, 2] 内没有会议。

示例 2：

输入：eventTime = 10, k = 1, startTime = [0,2,9], endTime = [1,4,10]
输出：6
解释：将会议 [2, 4] 重新安排到 [1, 3]，在时间 [3, 9] 内没有会议。

示例 3：

输入：eventTime = 5, k = 2, 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
  • 1 <= k <= n
  • 0 <= startTime[i] < endTime[i] <= eventTime
  • endTime[i] <= startTime[i + 1]，其中 i 在范围 [0, n - 2] 内

解题思路

解题思路

这道题的核心思路是利用滑动窗口来找到最优的重新安排方案。

关键观察：

  1. 由于要保持会议的相对顺序且不重叠，最优策略是将连续的 k 个会议紧密排列
  2. 如果我们选择重新安排 k 个连续会议，可以将它们移动到一个连续的时间段内
  3. 这样会创造出最大的连续空闲时间

算法步骤：

  1. 首先计算所有相邻会议之间的间隙，以及开始前和结束后的空隙
  2. 对于每个可能的 k 个连续会议的组合，计算如果将它们紧密排列能节省多少空间
  3. 使用滑动窗口技术，维护一个大小为 k+1 的窗口来计算间隙总和
  4. 窗口内的间隙可以通过重新排列会议来合并成一个大的空闲时间段

具体实现：

  • 创建间隙数组，包括开始前的间隙、会议间的间隙、结束后的间隙
  • 用滑动窗口找到 k+1 个间隙的最大总和
  • 这个最大总和就是能创造的最大连续空闲时间

代码实现

class Solution {
public:
    int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {
        int n = startTime.size();
        vector<int> gaps;
        
        // 添加开始前的间隙
        gaps.push_back(startTime[0]);
        
        // 添加会议间的间隙
        for (int i = 0; i < n - 1; i++) {
            gaps.push_back(startTime[i + 1] - endTime[i]);
        }
        
        // 添加结束后的间隙
        gaps.push_back(eventTime - endTime[n - 1]);
        
        // 滑动窗口找最大的 k+1 个间隙之和
        int windowSize = k + 1;
        int currentSum = 0;
        
        // 初始化窗口
        for (int i = 0; i < windowSize; i++) {
            currentSum += gaps[i];
        }
        
        int maxSum = currentSum;
        
        // 滑动窗口
        for (int i = windowSize; i < gaps.size(); i++) {
            currentSum += gaps[i] - gaps[i - windowSize];
            maxSum = max(maxSum, currentSum);
        }
        
        return maxSum;
    }
};

class Solution:
    def maxFreeTime(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int:
        n = len(startTime)
        gaps = []
        
        # 添加开始前的间隙
        gaps.append(startTime[0])
        
        # 添加会议间的间隙
        for i in range(n - 1):
            gaps.append(startTime[i + 1] - endTime[i])
        
        # 添加结束后的间隙
        gaps.append(eventTime - endTime[n - 1])
        
        # 滑动窗口找最大的 k+1 个间隙之和
        window_size = k + 1
        current_sum = sum(gaps[:window_size])
        max_sum = current_sum
        
        # 滑动窗口
        for i in range(window_size, len(gaps)):
            current_sum += gaps[i] - gaps[i - window_size]
            max_sum = max(max_sum, current_sum)
        
        return max_sum

public class Solution {
    public int MaxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        int n = startTime.Length;
        List<int> gaps = new List<int>();
        
        // 添加开始前的间隙
        gaps.Add(startTime[0]);
        
        // 添加会议间的间隙
        for (int i = 0; i < n - 1; i++) {
            gaps.Add(startTime[i + 1] - endTime[i]);
        }
        
        // 添加结束后的间隙
        gaps.Add(eventTime - endTime[n - 1]);
        
        // 滑动窗口找最大的 k+1 个间隙之和
        int windowSize = k + 1;
        int currentSum = 0;
        
        // 初始化窗口
        for (int i = 0; i < windowSize; i++) {
            currentSum += gaps[i];
        }
        
        int maxSum = currentSum;
        
        // 滑动窗口
        for (int i = windowSize; i < gaps.Count; i++) {
            currentSum += gaps[i] - gaps[i - windowSize];
            maxSum = Math.Max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}

var maxFreeTime = function(eventTime, k, startTime, endTime) {
    const n = startTime.length;
    const gaps = [];
    
    // 添加开始前的间隙
    gaps.push(startTime[0]);
    
    // 添加会议间的间隙
    for (let i = 0; i < n - 1; i++) {
        gaps.push(startTime[i + 1] - endTime[i]);
    }
    
    // 添加结束后的间隙
    gaps.push(eventTime - endTime[n - 1]);
    
    // 滑动窗口找最大的 k+1 个间隙之和
    const windowSize = k + 1;
    let currentSum = 0;
    
    // 初始化窗口
    for (let i = 0; i < windowSize; i++) {
        currentSum += gaps[i];
    }
    
    let maxSum = currentSum;
    
    // 滑动窗口
    for (let i = windowSize; i < gaps.length; i++) {
        currentSum += gaps[i] - gaps[i - windowSize];
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数值说明
时间复杂度O(n)需要遍历所有会议计算间隙，然后用滑动窗口遍历间隙数组
空间复杂度O(n)需要额外的数组存储间隙信息

相关题目