E3633.最早完成陆地和水上游乐设施的时间 I

greedy, https://leetcode.cn/problems/earliest-finish-time-for-land-and-water-rides-i/

给你两种类别的游乐园项目：陆地游乐设施 和 水上游乐设施。

陆地游乐设施
- landStartTime[i] – 第 i 个陆地游乐设施最早可以开始的时间。
- landDuration[i] – 第 i 个陆地游乐设施持续的时间。
水上游乐设施
- waterStartTime[j] – 第 j 个水上游乐设施最早可以开始的时间。
- waterDuration[j] – 第 j 个水上游乐设施持续的时间。

一位游客必须从每个类别中体验 恰好****一个 游乐设施，顺序不限。

游乐设施可以在其开放时间开始，或 之后任意时间 开始。
如果一个游乐设施在时间 t 开始，它将在时间 t + duration 结束。
完成一个游乐设施后，游客可以立即乘坐另一个（如果它已经开放），或者等待它开放。

返回游客完成这两个游乐设施的 最早可能时间 。

示例 1:

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

输出：9

解释：

方案 A（陆地游乐设施 0 → 水上游乐设施 0）：
- 在时间 landStartTime[0] = 2 开始陆地游乐设施 0。在 2 + landDuration[0] = 6 结束。
- 水上游乐设施 0 在时间 waterStartTime[0] = 6 开放。立即在时间 6 开始，在 6 + waterDuration[0] = 9 结束。
方案 B（水上游乐设施 0 → 陆地游乐设施 1）：
- 在时间 waterStartTime[0] = 6 开始水上游乐设施 0。在 6 + waterDuration[0] = 9 结束。
- 陆地游乐设施 1 在 landStartTime[1] = 8 开放。在时间 9 开始，在 9 + landDuration[1] = 10 结束。
方案 C（陆地游乐设施 1 → 水上游乐设施 0）：
- 在时间 landStartTime[1] = 8 开始陆地游乐设施 1。在 8 + landDuration[1] = 9 结束。
- 水上游乐设施 0 在 waterStartTime[0] = 6 开放。在时间 9 开始，在 9 + waterDuration[0] = 12 结束。
方案 D（水上游乐设施 0 → 陆地游乐设施 0）：
- 在时间 waterStartTime[0] = 6 开始水上游乐设施 0。在 6 + waterDuration[0] = 9 结束。
- 陆地游乐设施 0 在 landStartTime[0] = 2 开放。在时间 9 开始，在 9 + landDuration[0] = 13 结束。

方案 A 提供了最早的结束时间 9。

示例 2:

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

输出：14

解释：

方案 A（水上游乐设施 0 → 陆地游乐设施 0）：
- 在时间 waterStartTime[0] = 1 开始水上游乐设施 0。在 1 + waterDuration[0] = 11 结束。
- 陆地游乐设施 0 在 landStartTime[0] = 5 开放。立即在时间 11 开始，在 11 + landDuration[0] = 14 结束。
方案 B（陆地游乐设施 0 → 水上游乐设施 0）：
- 在时间 landStartTime[0] = 5 开始陆地游乐设施 0。在 5 + landDuration[0] = 8 结束。
- 水上游乐设施 0 在 waterStartTime[0] = 1 开放。立即在时间 8 开始，在 8 + waterDuration[0] = 18 结束。

方案 A 提供了最早的结束时间 14。****

提示:

1 <= n, m <= 100
landStartTime.length == landDuration.length == n
waterStartTime.length == waterDuration.length == m
1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 1000

一个可行且高效的方法是遍历所有可能的陆地游乐设施和水上游乐设施的组合，分别计算“先体验陆地项目再体验水上项目”以及“先体验水上项目再体验陆地项目”的结束时间，并求出全局最小值。

算法步骤

对于每一个陆地游乐设施 $i$ （其开始时间为 landStartTime[i]，持续时间为 landDuration[i]）和水上游乐设施 $j$ （其开始时间为 waterStartTime[j]，持续时间为 waterDuration[j]）：

先进行陆地游乐设施 $i$ ，后进行水上游乐设施 $j$ ：
- 陆地项目的结束时间为 $E_{l a n d} = landStartTime [i] + landDuration [i]$ 。
- 随后，水上项目最早可以在 $max (E_{l a n d}, waterStartTime [j])$ 开始，其完成时间为 $max (E_{l a n d}, waterStartTime [j]) + waterDuration [j]$ 。
先进行水上游乐设施 $j$ ，后进行陆地游乐设施 $i$ ：
- 水上项目的结束时间为 $E_{w a t e r} = waterStartTime [j] + waterDuration [j]$ 。
- 随后，陆地项目最早可以在 $max (E_{w a t e r}, landStartTime [i])$ 开始，其完成时间为 $max (E_{w a t e r}, landStartTime [i]) + landDuration [i]$ 。

通过遍历所有 $(i, j)$ 对（其中 $i \in [0, n - 1]$ ， $j \in [0, m - 1]$ ），并维护以上两种方案的最小值，即可求得最早完成两个游乐设施的时间。

Python 代码实现

python

from typing import List

class Solution:
    def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
        n = len(landStartTime)
        m = len(waterStartTime)
        min_finish_time = float('inf')
        
        for i in range(n):
            lst = landStartTime[i]
            ldu = landDuration[i]
            land_end = lst + ldu
            
            for j in range(m):
                wst = waterStartTime[j]
                wdu = waterDuration[j]
                water_end = wst + wdu
                
                # 方案一：先陆地，后水上
                finish_1 = max(land_end, wst) + wdu
                
                # 方案二：先水上，后陆地
                finish_2 = max(water_end, lst) + ldu
                
                # 更新全局最小值
                if finish_1 < min_finish_time:
                    min_finish_time = finish_1
                if finish_2 < min_finish_time:
                    min_finish_time = finish_2
                    
        return min_finish_time

复杂度分析

时间复杂度： $O (n \times m)$ 。其中 $n$ 为陆地游乐设施的数量， $m$ 为水上游乐设施的数量。由于题目中 $n, m \leq 100$ ，最大循环次数约为 $10^{4}$ ，能够在极短时间内运行完毕。
空间复杂度： $O (1)$ 。仅使用了若干变量来记录状态，不需要额外的辅助存储空间。

E3633.最早完成陆地和水上游乐设施的时间 I ​

E3633.最早完成陆地和水上游乐设施的时间 I