What is the optimal solution for 'Earliest Finish Time for Land and Water Rides I'?

The optimal solution can be achieved by using sorting to reduce unnecessary brute force comparisons, improving efficiency.

How do I approach the problem if brute force is too slow?

You can optimize by sorting the rides and applying a greedy or other efficient approach to minimize the finish time.

Can I solve 'Earliest Finish Time for Land and Water Rides I' with a greedy algorithm?

Yes, a greedy approach can help by selecting the best ride at each step, minimizing the total time.

How do I deal with edge cases in 'Earliest Finish Time for Land and Water Rides I'?

Ensure that all possible ride combinations are considered, including cases where there is only one ride in each category.

What is the time complexity of the brute force approach?

The brute force approach has a time complexity of O(n * m), where n is the number of land rides and m is the number of water rides.

#3633

Easy

auto_awesomeearliest·finish·time·for·land·water·rides·i·core·interview·pattern

LeetCode 题解工作台

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

给你两种类别的游乐园项目：陆地游乐设施和水上游乐设施。陆地游乐设施 landStartTime[i] – 第 i 个陆地游乐设施最早可以开始的时间。 landDuration[i] – 第 i 个陆地游乐设施持续的时间。水上游乐设施 waterStartTime[j] – 第 j 个水上…

题目描述

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

陆地游乐设施
- 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

lightbulb

解题思路

方法一：枚举 + 贪心

我们可以考虑两种游乐设施的顺序，先玩陆地游乐设施再玩水上游乐设施，或者先玩水上游乐设施再玩陆地游乐设施。

对于每种顺序，我们先计算出第一种游乐设施的最早结束时间 $\textit{minEnd}$ ，然后枚举第二种游乐设施，计算出第二种游乐设施的最早结束时间 $\max(\textit{minEnd}, \textit{startTime}) + \textit{duration}$ ，其中 $\textit{startTime}$ 是第二种游乐设施的开始时间。我们取所有可能的最早结束时间的最小值作为答案。

最后，我们返回两种顺序的答案中的最小值。

时间复杂度 $O(n + m)$ ，其中 $n$ 和 $m$ 分别是陆地游乐设施和水上游乐设施的数量。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
        def calc(a1, t1, a2, t2):
            min_end = min(a + t for a, t in zip(a1, t1))
            return min(max(a, min_end) + t for a, t in zip(a2, t2))

        x = calc(landStartTime, landDuration, waterStartTime, waterDuration)
        y = calc(waterStartTime, waterDuration, landStartTime, landDuration)
        return min(x, y)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate identify when brute force might be too slow for larger inputs?
question_mark
Does the candidate understand the trade-offs between brute force and optimization techniques like sorting or greedy algorithms?
question_mark
Is the candidate able to balance time complexity and correctness in their approach?

warning

常见陷阱

外企场景

error
Forgetting to consider both possible orders of land and water rides.
error
Not optimizing the brute force solution by using sorting or other strategies.
error
Overlooking edge cases such as having only one ride in each category.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if there are multiple water rides and land rides with overlapping start times?
arrow_right_alt
How would the solution change if a fixed order of rides (land first or water first) is required?
arrow_right_alt
What if you need to account for ride maintenance that causes some rides to be unavailable at certain times?

help

常见问题

外企场景

探索更多题目 →

auto_awesome

继续模式

earliest·finish·time·for·land·water·rides·i·core·interview·pattern

用同一解题框架扩展到更多题目。

arrow_forward signal_cellular_alt

同难度题单

简单

按当前难度继续强化稳定输出。

arrow_forward