LeetCode 3967. 最早完成陆地和水上游乐设施的时间 II

题目描述

给定两类游乐园项目：陆地游乐设施 和 水上游乐设施，每个设施有最早开始时间和持续时间。游客必须从每个类别中体验恰好一个设施，顺序不限。设施可以在其开放时间或之后任意时间开始。返回完成两个设施的最早可能时间。

提示： 1 <= n, m <= 5 * 10^4

示例

示例 1：

输入：landStartTime = [2,8], landDuration = [4,1], waterStartTime = [6], waterDuration = [3]
输出：9

示例 2：

输入：landStartTime = [5], landDuration = [3], waterStartTime = [1], waterDuration = [10]
输出：14

解题思路

核心观察

游客有两种顺序选择：陆地→水上 或 水上→陆地。对于每种顺序：

1. 陆地→水上：先完成陆地设施，再开始水上设施。陆地设施的最优选择是 landEnd = landStart[i] + landDuration[i] 最小的那个，因为越早完成陆地设施，水上设施就能越早开始。然后遍历所有水上设施，计算 max(waterStart[j], minLandEnd) + waterDuration[j]，取最小值。

2. 水上→陆地：同理，先完成水上设施，最优选择是 waterEnd 最小的那个，然后遍历所有陆地设施。

为什么选 landEnd 最小的陆地设施？

对于「陆地→水上」的顺序，陆地设施完成后才能开始水上设施。陆地设施完成时间越早，水上设施的开始时间就越早（或不受影响），因此选择 landEnd 最小的陆地设施一定是最优的。

复杂度分析

• 时间复杂度：O(n + m)，线性扫描即可
• 空间复杂度：O(1)

Python3 代码

class Solution:
    def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
        n = len(landStartTime)
        m = len(waterStartTime)
        
        # 分别找到陆地和水上设施最早完成时间
        minLandEnd = min(landStartTime[i] + landDuration[i] for i in range(n))
        minWaterEnd = min(waterStartTime[j] + waterDuration[j] for j in range(m))
        
        ans = float('inf')
        
        # 方案一：陆地 → 水上
        for j in range(m):
            finish = max(waterStartTime[j], minLandEnd) + waterDuration[j]
            ans = min(ans, finish)
        
        # 方案二：水上 → 陆地
        for i in range(n):
            finish = max(landStartTime[i], minWaterEnd) + landDuration[i]
            ans = min(ans, finish)
        
        return ans

提交结果

• 状态：✅ Accepted
• 通过用例：627 / 627
• 运行时间：115 ms
• 内存消耗：33 MB

总结

本题的关键在于贪心思想：对于先玩的那个类别，选择最早完成的设施一定是最优的。这样将问题从 O(n×m) 的暴力枚举优化到 O(n+m) 的线性扫描，轻松通过所有测试用例。