3439.重新安排会议得到最多空余时间 I：贪心(滑动窗口) - 连开k场会议

【LetMeFly】3439.重新安排会议得到最多空余时间 I：贪心(滑动窗口) - 连开k场会议

力扣题目链接：https://leetcode.cn/problems/reschedule-meetings-for-maximum-free-time-i/

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

解题方法：滑动窗口

解题思路

怎么尽可能出现“最大间隙”？当然是尽可能地把会议放到一块开。

题外话：长痛不如短痛，一下连着把课上了然后连着放个长假挺好的。

但是，我们最多调整k个会议的时间。怎么调？选连续的k个挤到一块呗（把当前选中的k个放到上次会议的end之后紧挨着）。

每次把连续的$k$个会议往前调后，k场会议中最后一个的结束时间和下一场会议的start之间的间隔即为调整这k个会议的情况下所能营造的最长连续间隔。

具体方法

首先将前k场会议统一挪到0时刻开始紧挨着k场。我们把这k场视为“窗口”，那么下一个“窗口”就是这次窗口右移一位（加上下一场会议减去第一场会议）。

使用一个变量cnt记录当前窗口中k场会议的总时间，根据（其实只需要加上→）窗口的上一场会议的结束时间就能得到这k场会议全部结束的时间了。

时空复杂度分析

• 时间复杂度$O(len(startTime))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-07-13 21:44:10
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-07-13 22:03:24
 */
class Solution {
public:
    int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {
        int cnt = 0;
        for (int i = 0; i < k; i++) {
            cnt += endTime[i] - startTime[i];
        }
        int ans = 0;
        int n = startTime.size();
        for (int i = k; i <= n; i++) {
            int l = (i == k ? 0 : endTime[i - k - 1]) + cnt;
            int r = (i == n ? eventTime : startTime[i]);
            ans = max(ans, r - l);
            // printf("i = %d, l = %d, r = %d, cnt = %d, ans = %d\n", i, l, r, cnt, ans);
            if (i == n) {
                break;
            }
            cnt += endTime[i] - startTime[i];
            cnt -= endTime[i - k] - startTime[i - k];
        }
        return ans;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-07-13 21:44:10
LastEditors: LetMeFly.xyz
LastEditTime: 2025-07-13 22:11:54
'''
from typing import List

class Solution:
    def maxFreeTime(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int:
        cnt = sum(endTime[i] - startTime[i] for i in range(k))
        n = len(startTime)
        ans = 0
        for i in range(k, n + 1):
            l = (endTime[i - k - 1] if i > k else 0) + cnt
            r = eventTime if i == n else startTime[i]
            ans = max(ans, r - l)
            if i == n:
                break
            cnt += endTime[i] - startTime[i]
            cnt -= endTime[i - k] - startTime[i - k]
        return ans

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-07-13 21:44:10
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-07-13 22:17:13
 */
class Solution {
    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        int cnt = 0;
        for (int i = 0; i < k; i++) {
            cnt += endTime[i] - startTime[i];
        }
        int n = startTime.length;
        int ans = 0;
        for (int i = k; i <= n; i++) {
            int l = (i == k ? 0 : endTime[i - k - 1]) + cnt;
            int r = i == n ? eventTime : startTime[i];
            ans = Math.max(ans, r - l);
            if (i == n) {
                break;
            }
            cnt += endTime[i] - startTime[i];
            cnt -= endTime[i - k] - startTime[i - k];
        }
        return ans;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-07-13 21:44:10
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-07-13 22:23:03
 */
package main

func maxFreeTime(eventTime int, k int, startTime []int, endTime []int) (ans int) {
    cnt := 0
    for i := 0; i < k; i++ {
        cnt += endTime[i] - startTime[i]
    }
    n := len(startTime)
    for i := k; i <= n; i++ {
        var l, r int
        if i == k {
            l = cnt
        } else {
            l = endTime[i - k - 1] + cnt
        }
        if i == n {
            r = eventTime
        } else {
            r = startTime[i]
        }
        ans = max(ans, r - l)
        if i == n {
            break
        }
        cnt += endTime[i] - startTime[i]
        cnt -= endTime[i - k] - startTime[i - k]
    }
    return ans
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源