Medium
题目描述
你有两类主题公园景点：陆地游乐设施和水上游乐设施。
陆地游乐设施
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 <= 5 * 10^4landStartTime.length == landDuration.length == nwaterStartTime.length == waterDuration.length == m1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 10^5
解题思路
这是一道组合优化问题，需要考虑两种顺序：先玩陆地设施再玩水上设施，或先玩水上设施再玩陆地设施。
核心思路：
- 对每类设施按开始时间排序，构建前缀最小持续时间数组和后缀最小结束时间数组
- 对于两种顺序分别计算：
- 先陆地后水上：对每个陆地设施，用二分搜索找到水上设施中哪些在陆地设施结束时已开放，哪些还未开放
- 先水上后陆地：类似处理
优化策略：
- 对于已开放的设施，选择持续时间最短的（前缀最小值）
- 对于未开放的设施，选择结束时间最早的（后缀最小值）
- 使用二分搜索快速定位分界点
算法步骤：
- 预处理：对设施按开始时间排序，计算前缀最小持续时间和后缀最小结束时间
- 尝试先陆地后水上的顺序，对每个陆地设施计算最优搭配
- 尝试先水上后陆地的顺序，对每个水上设施计算最优搭配
- 返回所有可能方案中的最小值
时间复杂度主要来自排序和二分搜索，空间复杂度用于存储前缀后缀数组。
代码实现
class Solution {
public:
int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration, vector<int>& waterStartTime, vector<int>& waterDuration) {
int n = landStartTime.size(), m = waterStartTime.size();
// 构建陆地设施数组 (start, duration, finish)
vector<array<int, 3>> land(n), water(m);
for (int i = 0; i < n; i++) {
land[i] = {landStartTime[i], landDuration[i], landStartTime[i] + landDuration[i]};
}
for (int i = 0; i < m; i++) {
water[i] = {waterStartTime[i], waterDuration[i], waterStartTime[i] + waterDuration[i]};
}
// 按开始时间排序
sort(land.begin(), land.end());
sort(water.begin(), water.end());
auto solve = [&](vector<array<int, 3>>& first, vector<array<int, 3>>& second) -> int {
int m = second.size();
vector<int> prefixMinDuration(m), suffixMinFinish(m);
// 前缀最小持续时间
prefixMinDuration[0] = second[0][1];
for (int i = 1; i < m; i++) {
prefixMinDuration[i] = min(prefixMinDuration[i-1], second[i][1]);
}
// 后缀最小结束时间
suffixMinFinish[m-1] = second[m-1][2];
for (int i = m-2; i >= 0; i--) {
suffixMinFinish[i] = min(suffixMinFinish[i+1], second[i][2]);
}
int result = INT_MAX;
for (auto& ride : first) {
int finish1 = ride[2];
// 二分搜索找到第一个开始时间 > finish1 的位置
int pos = lower_bound(second.begin(), second.end(),
array<int, 3>{finish1 + 1, 0, 0}) - second.begin();
// 已开放的设施 (start <= finish1)
if (pos > 0) {
result = min(result, finish1 + prefixMinDuration[pos-1]);
}
// 未开放的设施 (start > finish1)
if (pos < m) {
result = min(result, suffixMinFinish[pos]);
}
}
return result;
};
// 尝试两种顺序
int ans1 = solve(land, water);
int ans2 = solve(water, land);
return min(ans1, ans2);
}
};
class Solution:
def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
import bisect
n, m = len(landStartTime), len(waterStartTime)
# 构建设施数组 (start, duration, finish)
land = [(landStartTime[i], landDuration[i], landStartTime[i] + landDuration[i]) for i in range(n)]
water = [(waterStartTime[i], waterDuration[i], waterStartTime[i] + waterDuration[i]) for i in range(m)]
# 按开始时间排序
land.sort()
water.sort()
def solve(first, second):
m = len(second)
if m == 0:
return float('inf')
# 前缀最小持续时间
prefix_min_duration = [0] * m
prefix_min_duration[0] = second[0][1]
for i in range(1, m):
prefix_min_duration[i] = min(prefix_min_duration[i-1], second[i][1])
# 后缀最小结束时间
suffix_min_finish = [0] * m
suffix_min_finish[m-1] = second[m-1][2]
for i in range(m-2, -1, -1):
suffix_min_finish[i] = min(suffix_min_finish[i+1], second[i][2])
result = float('inf')
starts = [ride[0] for ride in second]
for ride in first:
finish1 = ride[2]
# 二分搜索找到第一个开始时间 > finish1 的位置
pos = bisect.bisect_right(starts, finish1)
# 已开放的设施 (start <= finish1)
if pos > 0:
result = min(result, finish1 + prefix_min_duration[pos-1])
# 未开放的设施 (start > finish1)
if pos < m:
result = min(result, suffix_min_finish[pos])
return result
# 尝试两种顺序
ans1 = solve(land, water)
ans2 = solve(water, land)
return min(ans1, ans2)
public class Solution {
public int EarliestFinishTime(int[] landStartTime, int[] landDuration, int[] waterStartTime, int[] waterDuration) {
int n = landStartTime.Length, m = waterStartTime.Length;
// 构建设施数组
var land = new (int start, int duration, int finish)[n];
var water = new (int start, int duration, int finish)[m];
for (int i = 0; i < n; i++) {
land[i] = (landStartTime[i], landDuration[i], landStartTime[i] + landDuration[i]);
}
for (int i = 0; i < m; i++) {
water[i] = (waterStartTime[i], waterDuration[i], waterStartTime[i] + waterDuration[i]);
}
// 按开始时间排序
Array.Sort(land, (a, b) => a.start.CompareTo(b.start));
Array.Sort(water, (a, b) => a.start.CompareTo(b.start));
int Solve((int start, int duration, int finish)[] first, (int start, int duration, int finish)[] second) {
int len = second.Length;
if (len == 0) return int.MaxValue;
var prefixMinDuration = new int[len];
var suffixMinFinish = new int[len];
// 前缀最小持续时间
prefixMinDuration[0] = second[0].duration;
for (int i = 1; i < len; i++) {
prefixMinDuration[i] = Math.Min(prefixMinDuration[i-1], second[i].duration);
}
// 后缀最小结束时间
suffixMinFinish[len-1] = second[len-1].finish;
for (int i = len-2; i >= 0; i--) {
suffixMinFinish[i] = Math.Min(suffixMinFinish[i+1], second[i].finish);
}
int result = int.MaxValue;
foreach (var ride in first) {
int finish1 = ride.finish;
// 二分搜索
int left = 0, right = len;
while (left < right) {
int mid = (left + right) / 2;
if (second[mid].start <= finish1) {
left = mid + 1;
} else {
right = mid;
}
}
int pos = left;
// 已开放的设施
if (pos > 0) {
result = Math.Min(result, finish1 + prefixMinDuration[pos-1]);
}
// 未开放的设施
if (pos < len) {
result = Math.Min(result, suffixMinFinish[pos]);
}
}
return result;
}
// 尝试两种顺序
int ans1 = Solve(land, water);
int ans2 = Solve(water, land);
return Math.Min(ans1, ans2);
}
}
var earliestFinishTime = function(landStartTime, landDuration, waterStartTime, waterDuration) {
let minTime = Infinity;
// Try land ride first, then water ride
for (let i = 0; i < landStartTime.length; i++) {
let landFinish = landStartTime[i] + landDuration[i];
for (let j = 0; j < waterStartTime.length; j++) {
let waterStart = Math.max(landFinish, waterStartTime[j]);
let waterFinish = waterStart + waterDuration[j];
minTime = Math.min(minTime, waterFinish);
}
}
// Try water ride first, then land ride
for (let j = 0; j < waterStartTime.length; j++) {
let waterFinish = waterStartTime[j] + waterDuration[j];
for (let i = 0; i < landStartTime.length; i++) {
let landStart = Math.max(waterFinish, landStartTime[i]);
let landFinish = landStart + landDuration[i];
minTime = Math.min(minTime, landFinish);
}
}
return minTime;
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |