Easy

题目描述

给你两类主题公园游乐设施：陆地游乐设施和水上游乐设施。

陆地游乐设施

  • 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

示例 2：

输入：landStartTime = [5], landDuration = [3], waterStartTime = [1], waterDuration = [10]
输出：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

解题思路

解题思路

这道题要求找到完成陆地和水上游乐设施的最早时间。由于游客必须体验每类设施中的恰好一个，且可以任意选择顺序，我们需要考虑所有可能的组合。

暴力枚举法： 对于每个陆地设施和每个水上设施的组合，我们需要计算两种执行顺序的完成时间：

  1. 先玩陆地设施，再玩水上设施
  2. 先玩水上设施，再玩陆地设施

对于每种顺序，计算步骤如下：

  • 第一个设施在其开始时间开始，结束时间 = 开始时间 + 持续时间
  • 第二个设施的实际开始时间 = max(第一个设施结束时间, 第二个设施的最早开始时间)
  • 最终完成时间 = 第二个设施的实际开始时间 + 第二个设施的持续时间

由于数据规模较小（n, m ≤ 100），暴力枚举所有组合的时间复杂度 O(n×m) 完全可以接受。我们遍历所有可能的 (陆地设施, 水上设施) 组合，计算两种顺序的完成时间，取所有情况中的最小值。

代码实现

class Solution {
public:
    int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration, vector<int>& waterStartTime, vector<int>& waterDuration) {
        int minTime = INT_MAX;
        int n = landStartTime.size();
        int m = waterStartTime.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 先玩陆地设施，再玩水上设施
                int landFinish = landStartTime[i] + landDuration[i];
                int waterStart = max(landFinish, waterStartTime[j]);
                int time1 = waterStart + waterDuration[j];
                
                // 先玩水上设施，再玩陆地设施
                int waterFinish = waterStartTime[j] + waterDuration[j];
                int landStart = max(waterFinish, landStartTime[i]);
                int time2 = landStart + landDuration[i];
                
                minTime = min(minTime, min(time1, time2));
            }
        }
        
        return minTime;
    }
};

class Solution:
    def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
        min_time = float('inf')
        n, m = len(landStartTime), len(waterStartTime)
        
        for i in range(n):
            for j in range(m):
                # 先玩陆地设施，再玩水上设施
                land_finish = landStartTime[i] + landDuration[i]
                water_start = max(land_finish, waterStartTime[j])
                time1 = water_start + waterDuration[j]
                
                # 先玩水上设施，再玩陆地设施
                water_finish = waterStartTime[j] + waterDuration[j]
                land_start = max(water_finish, landStartTime[i])
                time2 = land_start + landDuration[i]
                
                min_time = min(min_time, min(time1, time2))
        
        return min_time

public class Solution {
    public int EarliestFinishTime(int[] landStartTime, int[] landDuration, int[] waterStartTime, int[] waterDuration) {
        int minTime = int.MaxValue;
        int n = landStartTime.Length;
        int m = waterStartTime.Length;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 先玩陆地设施，再玩水上设施
                int landFinish = landStartTime[i] + landDuration[i];
                int waterStart = Math.Max(landFinish, waterStartTime[j]);
                int time1 = waterStart + waterDuration[j];
                
                // 先玩水上设施，再玩陆地设施
                int waterFinish = waterStartTime[j] + waterDuration[j];
                int landStart = Math.Max(waterFinish, landStartTime[i]);
                int time2 = landStart + landDuration[i];
                
                minTime = Math.Min(minTime, Math.Min(time1, time2));
            }
        }
        
        return minTime;
    }
}

var earliestFinishTime = function(landStartTime, landDuration, waterStartTime, waterDuration) {
    let minTime = Infinity;
    const n = landStartTime.length;
    const m = waterStartTime.length;
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            // 先玩陆地设施，再玩水上设施
            const landFinish = landStartTime[i] + landDuration[i];
            const waterStart = Math.max(landFinish, waterStartTime[j]);
            const time1 = waterStart + waterDuration[j];
            
            // 先玩水上设施，再玩陆地设施
            const waterFinish = waterStartTime[j] + waterDuration[j];
            const landStart = Math.max(waterFinish, landStartTime[i]);
            const time2 = landStart + landDuration[i];
            
            minTime = Math.min(minTime, Math.min(time1, time2));
        }
    }
    
    return minTime;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × m)需要遍历所有陆地设施和水上设施的组合，每个组合需要计算两种顺序
空间复杂度O(1)只使用常数额外空间