qzy's blog

力扣每日一题-2025-07-09

2025/07/09 算法 共 2607 字，约 8 分钟

问题描述

力扣链接

给定一个活动的总时长 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. 准备时间数组：

    • 在会议的结束时间前加入一个虚拟的起始时间 0，在会议的开始时间后加入一个虚拟的结束时间 eventTime。

  2. 计算间隔时间：

    • 计算相邻会议时间段的间隔时间，得到一个新的列表。

  3. 滑动窗口：

    • 使用卷积（convolution）操作来模拟移动会议的效果。通过移动 k 次来尽可能拉大空闲时间。

  4. 获取最大空余时间：

    • 返回最大化后的空余时间。

代码实现

import numpy as np

class Solution(object):
    def maxFreeTime(self, eventTime, k, startTime, endTime):
        """
        :type eventTime: int
        :type k: int
        :type startTime: List[int]
        :type endTime: List[int]
        :rtype: int
        """
        # 在会议的结束时间前加入虚拟的时间 0，在会议的开始时间后加入虚拟的时间 eventTime
        endTime_mod = [0] + endTime
        startTime_mod = startTime + [eventTime]
        
        # 计算相邻会议之间的空余时间
        sublist = [startTime_mod[i] - endTime_mod[i] for i in range(len(startTime_mod))]
        
        # 将最多 k 个会议进行移动，使用卷积计算空余时间
        k = k + 1
        kernel = np.ones(k)  # 卷积核
        convolved = np.convolve(sublist, kernel, mode='valid')  # 卷积操作，返回所有的空余时间

        # 返回最大空余时间
        return int(max(convolved))

代码解释

  1. endTime_mod = [0] + endTime 和 startTime_mod = startTime + [eventTime]

    • 我们通过给 endTime 数组前加一个 0，给 startTime 数组后加一个 eventTime，来模拟活动的起始和结束边界。

  2. sublist = [startTime_mod[i] - endTime_mod[i] for i in range(len(startTime_mod))]

    • 计算每一对会议之间的空余时间，这通过将每个会议的开始时间与前一个会议的结束时间进行相减来完成。

  3. kernel = np.ones(k) 和 convolved = np.convolve(sublist, kernel, mode='valid')

    • 使用卷积操作来模拟移动 k 个会议后的最大空余时间。卷积操作会计算多个空余时间段的总和，从而找出能最大化空余时间的最优方案。

  4. return int(max(convolved))

    • 最后，返回通过卷积操作获得的最大空余时间。

优化思路

可以进一步优化：

优化 1：滑动窗口实现

通过滑动窗口直接计算每次移动后的空余时间和，避免使用卷积操作。

优化后的代码：

class Solution(object):
    def maxFreeTime(self, eventTime, k, startTime, endTime):
        """
        :type eventTime: int
        :type k: int
        :type startTime: List[int]
        :type endTime: List[int]
        :rtype: int
        """
        # 添加虚拟的开始和结束时间
        endTime_mod = [0] + endTime
        startTime_mod = startTime + [eventTime]
        
        # 计算相邻会议之间的空余时间
        sublist = [startTime_mod[i] - endTime_mod[i] for i in range(len(startTime_mod))]
        
        # 使用滑动窗口来计算最多k次会议的移动后的最大空余时间
        # 初始化窗口的和
        window_sum = sum(sublist[:k+1])
        max_free_time = window_sum
        
        for i in range(k+1, len(sublist)):
            # 滑动窗口，移除左边的元素，加入右边的元素
            window_sum += sublist[i] - sublist[i - (k+1)]
            max_free_time = max(max_free_time, window_sum)
        
        return int(max_free_time)

优化点：

  • 滑动窗口替代卷积：通过滑动窗口计算相邻会议之间的空闲时间和，减少了内存的使用。
  • 减少内存使用：只保留当前窗口的总和，而不是计算和存储所有中间结果。

复杂度分析

  • 时间复杂度：O(n)，其中 n 是 startTime 和 endTime 数组的长度。滑动窗口操作的时间复杂度为 O(n)，卷积操作的时间复杂度为 O(n)。
  • 空间复杂度：O(n)，我们需要存储 sublist 和进行滑动窗口操作的结果。

总结

通过使用滑动窗口来优化空闲时间的计算，可以有效减少不必要的内存消耗，同时提高计算效率。这个优化不仅提高了代码的性能，还使得内存的使用更为高效。

文档信息

Search

    Table of Contents