2026-01-05：最早完成陆地和水上游乐设施的时间Ⅰ。用go语言，有两类项目：陆地和水上。每个陆地项目有最早可开的时间 a_i 与持续时长 d_

福大大架构师每日一题

发布于 2026-01-12 11:09:23

1110

2026-01-05：最早完成陆地和水上游乐设施的时间Ⅰ。用go语言，有两类项目：陆地和水上。每个陆地项目有最早可开的时间 a_i 与持续时长 d_i，水上项目有最早开时 b_j 与时长 e_j。游客须各选一项（先后顺序可选），任意项目可在其最早开时或之后任何时刻启动，若在 t 时开始则在 t+持续时长结束；完成第一个后可立刻乘坐或等候第二个开放。求能在两项都完成的前提下，最早能达到的结束时间。

1 <= n, m <= 100。

landStartTime.length == landDuration.length == n。

waterStartTime.length == waterDuration.length == m。

1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 1000。

输入：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。

题目来自力扣3633。

计算过程分步描述

1. 计算陆地项目的最早可能完成时间：代码首先遍历所有陆地项目。对于每个项目，计算如果立即在其最早开始时间启动，它的结束时间（landStartTime[i] + landDuration[i]）。然后，找出所有陆地项目中最小的结束时间，记为 minFinish。这个值代表了如果先玩陆地项目，整个流程中陆地部分可能的最早完成时间点。
2. 模拟“先陆地后水上”的流程：接着，代码遍历所有水上项目。对于每个水上项目，计算在“陆地项目已完成”这个前提下，开始玩水上项目的时间。这个开始时间取决于两个因素：水上项目自身的开放时间（waterStartTime[i]）和陆地项目的最早完成时间（minFinish）。游客必须等到两者中较晚的时间点才能开始水上项目，即开始时间为 max(waterStartTime[i], minFinish)。然后，加上水上项目的持续时间（waterDuration[i]），就得到了“先陆地后水上”这种顺序下，选择当前这个水上项目的总完成时间。代码会记录所有水上项目中最小的总完成时间，存入变量 res。这个 res 就是“先陆地后水上”顺序下的最优解。
3. 模拟“先水上后陆地”的流程：为了找到全局最优解，必须考虑另一种顺序。代码通过调用同一个 solve 函数，但交换陆地和水上项目的参数来实现。这一次，函数会先找出所有水上项目中最小的结束时间，作为水上部分的最早完成时间。然后，同样遍历所有陆地项目，计算开始时间为 max(landStartTime[i], 水上项目最早完成时间)，并加上陆地项目的持续时间，最终得到“先水上后陆地”顺序下的最优完成时间。
4. 比较两种顺序，得出最终答案：最后，代码比较“先陆地后水上”（landWater）和“先水上后陆地”（waterLand）两种顺序下得到的最优完成时间，取其中的较小值作为最终的答案。这确保了找到了所有可能方案中的最早完成时间。

复杂度分析

• 总的时间复杂度：O(n + m)，其中 n 是陆地项目的数量，m 是水上项目的数量。
- • 计算过程的核心是两次 solve 函数的调用。每次 solve 函数都包含两个独立的循环：第一个循环遍历一类项目（如陆地项目）以计算最小结束时间，复杂度为 O(n) 或 O(m)；第二个循环遍历另一类项目（如水上项目）以计算最终完成时间，复杂度为 O(m) 或 O(n)。
- • 因此，总的时间复杂度是 O(n + m) + O(m + n) = O(2*(n + m))，根据大O表示法的规则，常数因子可以忽略，所以是 O(n + m)。这比暴力检查所有项目组合（O(n * m)）要高效得多。
• 总的额外空间复杂度：O(1)。
- • 算法运行过程中只使用了固定数量的额外变量（如 minFinish, res, i 等）来存储中间结果和循环索引。这些变量的数量不随输入数据规模（n 和 m）的增长而增长。
- • 因此，额外的空间复杂度是常数级别的 O(1)。

Go完整代码如下：

package main

import (
    "fmt"
    "math"
)

func solve(landStartTime, landDuration, waterStartTime, waterDuration []int)int {
    minFinish := math.MaxInt
    for i, start := range landStartTime {
        minFinish = min(minFinish, start+landDuration[i])
    }

    res := math.MaxInt
    for i, start := range waterStartTime {
        res = min(res, max(start, minFinish)+waterDuration[i])
    }
    return res
}

func earliestFinishTime(landStartTime, landDuration, waterStartTime, waterDuration []int)int {
    landWater := solve(landStartTime, landDuration, waterStartTime, waterDuration)
    waterLand := solve(waterStartTime, waterDuration, landStartTime, landDuration)
    return min(landWater, waterLand)
}

func main() {
    landStartTime := []int{5}
    landDuration := []int{3}
    waterStartTime := []int{1}
    waterDuration := []int{10}
    result := earliestFinishTime(landStartTime, landDuration, waterStartTime, waterDuration)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

def solve(start_a: List[int], duration_a: List[int], start_b: List[int], duration_b: List[int]) -> int:
    min_finish = float('inf')
    for i, start in enumerate(start_a):
        min_finish = min(min_finish, start + duration_a[i])

    res = float('inf')
    for i, start in enumerate(start_b):
        res = min(res, max(start, min_finish) + duration_b[i])
    return res

def earliest_finish_time(land_start_time: List[int], land_duration: List[int],
                         water_start_time: List[int], water_duration: List[int]) -> int:
    land_water = solve(land_start_time, land_duration, water_start_time, water_duration)
    water_land = solve(water_start_time, water_duration, land_start_time, land_duration)
    return min(land_water, water_land)

if __name__ == "__main__":
    land_start_time = [5]
    land_duration = [3]
    water_start_time = [1]
    water_duration = [10]
    result = earliest_finish_time(land_start_time, land_duration, water_start_time, water_duration)
    print(result)

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int solve(const vector<int>& startA, const vector<int>& durationA,
          const vector<int>& startB, const vector<int>& durationB) {
    int minFinish = INT_MAX;
    for (size_t i = 0; i < startA.size(); ++i) {
        minFinish = min(minFinish, startA[i] + durationA[i]);
    }

    int res = INT_MAX;
    for (size_t i = 0; i < startB.size(); ++i) {
        res = min(res, max(startB[i], minFinish) + durationB[i]);
    }
    return res;
}

int earliestFinishTime(const vector<int>& landStartTime, const vector<int>& landDuration,
                       const vector<int>& waterStartTime, const vector<int>& waterDuration) {
    int landWater = solve(landStartTime, landDuration, waterStartTime, waterDuration);
    int waterLand = solve(waterStartTime, waterDuration, landStartTime, landDuration);
    return min(landWater, waterLand);
}

int main() {
    vector<int> landStartTime = {5};
    vector<int> landDuration = {3};
    vector<int> waterStartTime = {1};
    vector<int> waterDuration = {10};

    int result = earliestFinishTime(landStartTime, landDuration, waterStartTime, waterDuration);
    cout << result << endl;

    return0;
}