3633. 最早完成陆地和水上游乐设施的时间 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

解法

方法一：枚举 + 贪心

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

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

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

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

Python3JavaC++GoTypeScript

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)

class Solution {
    public int earliestFinishTime(
        int[] landStartTime, int[] landDuration, int[] waterStartTime, int[] waterDuration) {
        int x = calc(landStartTime, landDuration, waterStartTime, waterDuration);
        int y = calc(waterStartTime, waterDuration, landStartTime, landDuration);
        return Math.min(x, y);
    }

    private int calc(int[] a1, int[] t1, int[] a2, int[] t2) {
        int minEnd = Integer.MAX_VALUE;
        for (int i = 0; i < a1.length; ++i) {
            minEnd = Math.min(minEnd, a1[i] + t1[i]);
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < a2.length; ++i) {
            ans = Math.min(ans, Math.max(minEnd, a2[i]) + t2[i]);
        }
        return ans;
    }
}

class Solution {
public:
    int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration, vector<int>& waterStartTime, vector<int>& waterDuration) {
        int x = calc(landStartTime, landDuration, waterStartTime, waterDuration);
        int y = calc(waterStartTime, waterDuration, landStartTime, landDuration);
        return min(x, y);
    }

    int calc(vector<int>& a1, vector<int>& t1, vector<int>& a2, vector<int>& t2) {
        int minEnd = INT_MAX;
        for (int i = 0; i < a1.size(); ++i) {
            minEnd = min(minEnd, a1[i] + t1[i]);
        }
        int ans = INT_MAX;
        for (int i = 0; i < a2.size(); ++i) {
            ans = min(ans, max(minEnd, a2[i]) + t2[i]);
        }
        return ans;
    }
};

func earliestFinishTime(landStartTime []int, landDuration []int, waterStartTime []int, waterDuration []int) int {
    x := calc(landStartTime, landDuration, waterStartTime, waterDuration)
    y := calc(waterStartTime, waterDuration, landStartTime, landDuration)
    return min(x, y)
}

func calc(a1 []int, t1 []int, a2 []int, t2 []int) int {
    minEnd := math.MaxInt32
    for i := 0; i < len(a1); i++ {
        minEnd = min(minEnd, a1[i]+t1[i])
    }
    ans := math.MaxInt32
    for i := 0; i < len(a2); i++ {
        ans = min(ans, max(minEnd, a2[i])+t2[i])
    }
    return ans
}

function earliestFinishTime(
    landStartTime: number[],
    landDuration: number[],
    waterStartTime: number[],
    waterDuration: number[],
): number {
    const x = calc(landStartTime, landDuration, waterStartTime, waterDuration);
    const y = calc(waterStartTime, waterDuration, landStartTime, landDuration);
    return Math.min(x, y);
}

function calc(a1: number[], t1: number[], a2: number[], t2: number[]): number {
    let minEnd = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < a1.length; i++) {
        minEnd = Math.min(minEnd, a1[i] + t1[i]);
    }
    let ans = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < a2.length; i++) {
        ans = Math.min(ans, Math.max(minEnd, a2[i]) + t2[i]);
    }
    return ans;
}

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

题目描述

解法

方法一：枚举 + 贪心

评论