日期：2026年6月3日
LeetCode 題目連結：3635. Earliest Finish Time for Land and Water Rides II
解題想法
3633. Earliest Finish Time for Land and Water Rides I 的加強版，由於測資數量大很多，不能用簡單版的寫法，速度太慢。
Python 程式碼
Runtime: 778 ms, beats 7.27%. Memory: 39.98 MB, beats 12.73%.
from bisect import bisect_right
class Solution:
def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
n, m = len(landStartTime), len(waterStartTime)
# 合併開始、經過時刻，組成 (開始時刻, 經過時間)
land = list(zip(landStartTime, landDuration))
water = list(zip(waterStartTime, waterDuration))
land.sort() # 依照開始時刻排序
water.sort()
# 取出排序後的開始時刻，用於二分搜尋法
landStart = [s for s, _ in land]
waterStart = [s for s, _ in water]
# 前綴最短持續時間
landDurationMin = [0] * n
landDurationMin[0] = land[0][1]
for i in range(1, n):
landDurationMin[i] = min(landDurationMin[i-1], land[i][1])
waterDurationMin = [0] * m
waterDurationMin[0] = water[0][1]
for i in range(1, m):
waterDurationMin[i] = min(waterDurationMin[i-1], water[i][1])
# 後綴最早結束時刻
landFinishMin = [0] * n
landFinishMin[-1] = land[-1][0] + land[-1][1]
for i in range(n-2, -1, -1):
landFinishMin[i] = min(landFinishMin[i+1], land[i][0] + land[i][1])
waterFinishMin = [0] * m
waterFinishMin[-1] = water[-1][0] + water[-1][1]
for i in range(m-2, -1, -1):
waterFinishMin[i] = min(waterFinishMin[i+1], water[i][0] + water[i][1])
# 先去 land 再去 water 的最早結束時刻
ans = float('inf') # 答案
for landS, landD in land:
landF = landS + landD # 結束時刻
# 用二分搜尋法從 waterStart 之中找分界點 idx
# idx 左側，已開放，可以直接玩
# idx 右側，尚未開放，要等一段時間
idx = bisect_right(waterStart, landF)
currMin = float('inf') # 目前的最短時間
# 狀況1，可以直接玩已開放的設施，取 landF 加上 0 ~ idx-1 最短持續時間
if idx > 0:
currMin = min(currMin, landF + waterDurationMin[idx - 1])
# 狀況2，等待還沒有開放的設施，取 idx ~ m-1 最早結束時刻
if idx < m:
currMin = min(currMin, waterFinishMin[idx])
# 更新 ans
ans = min(ans, currMin)
# 先去 water 再去 land 的最早結束時刻
for waterS, waterD in water:
waterF = waterS + waterD # 結束時刻
# 用二分搜尋法從 landStart 之中找分界點 idx
# idx 左側，已開放，可以直接玩
# idx 右側，尚未開放，要等一段時間
idx = bisect_right(landStart, waterF)
currMin = float('inf') # 目前的最短時間
# 狀況1，可以直接玩已開放的設施，取 waterF 加上 0 ~ idx-1 最短持續時間
if idx > 0:
currMin = min(currMin, waterF + landDurationMin[idx - 1])
# 狀況2，等待還沒有開放的設施，取 idx ~ n-1 最早結束時刻
if idx < n:
currMin = min(currMin, landFinishMin[idx])
# 更新 ans
ans = min(ans, currMin)
# 回傳答案
return ans
不呼叫 min，速度會快一點。Runtime: 763 ms, beats 7.27%. Memory: 39.84 MB, beats 12.73%.
from bisect import bisect_right
class Solution:
def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
n, m = len(landStartTime), len(waterStartTime)
# 合併開始、經過時刻，組成 (開始時刻, 經過時間)
land = list(zip(landStartTime, landDuration))
water = list(zip(waterStartTime, waterDuration))
land.sort() # 依照開始時刻排序
water.sort()
# 取出排序後的開始時刻，用於二分搜尋法
landStart = [s for s, _ in land]
waterStart = [s for s, _ in water]
# 前綴最短持續時間
landDurationMin = [0] * n
landDurationMin[0] = land[0][1]
for i in range(1, n):
landDurationMin[i] = landDurationMin[i-1]
if land[i][1] < landDurationMin[i]:
landDurationMin[i] = land[i][1]
waterDurationMin = [0] * m
waterDurationMin[0] = water[0][1]
for i in range(1, m):
waterDurationMin[i] = waterDurationMin[i-1]
if water[i][1] < waterDurationMin[i]:
waterDurationMin[i] = water[i][1]
# 後綴最早結束時刻
landFinishMin = [0] * n
landFinishMin[-1] = land[-1][0] + land[-1][1]
for i in range(n-2, -1, -1):
landFinishMin[i] = landFinishMin[i+1]
if land[i][0] + land[i][1] < landFinishMin[i]:
landFinishMin[i] = land[i][0] + land[i][1]
waterFinishMin = [0] * m
waterFinishMin[-1] = water[-1][0] + water[-1][1]
for i in range(m-2, -1, -1):
waterFinishMin[i] = waterFinishMin[i+1]
if water[i][0] + water[i][1] < waterFinishMin[i]:
waterFinishMin[i] = water[i][0] + water[i][1]
# 先去 land 再去 water 的最早結束時刻
ans = float('inf') # 答案
for landS, landD in land:
landF = landS + landD # 結束時刻
# 用二分搜尋法從 waterStart 之中找分界點 idx
# idx 左側，已開放，可以直接玩
# idx 右側，尚未開放，要等一段時間
idx = bisect_right(waterStart, landF)
currMin = float('inf') # 目前的最短時間
# 狀況1，可以直接玩已開放的設施，取 landF 加上 0 ~ idx-1 最短持續時間
if idx > 0:
if landF + waterDurationMin[idx - 1] < currMin:
currMin = landF + waterDurationMin[idx - 1]
# 狀況2，等待還沒有開放的設施，取 idx ~ m-1 最早結束時刻
if idx < m:
if waterFinishMin[idx] < currMin:
currMin = waterFinishMin[idx]
# 更新 ans
if currMin < ans: ans = currMin
# 先去 water 再去 land 的最早結束時刻
for waterS, waterD in water:
waterF = waterS + waterD # 結束時刻
# 用二分搜尋法從 landStart 之中找分界點 idx
# idx 左側，已開放，可以直接玩
# idx 右側，尚未開放，要等一段時間
idx = bisect_right(landStart, waterF)
currMin = float('inf') # 目前的最短時間
# 狀況1，可以直接玩已開放的設施，取 waterF 加上 0 ~ idx-1 最短持續時間
if idx > 0:
if waterF + landDurationMin[idx - 1] < currMin:
currMin = waterF + landDurationMin[idx - 1]
# 狀況2，等待還沒有開放的設施，取 idx ~ n-1 最早結束時刻
if idx < n:
if landFinishMin[idx] < currMin:
currMin = landFinishMin[idx]
# 更新 ans
if currMin < ans: ans = currMin
# 回傳答案
return ans
C++ 程式碼
Runtime: 132 ms, beats 19.27%. Memory: 262.45 MB, beats 18.35%.
#include <algorithm>
class Solution {
public:
int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration, vector<int>& waterStartTime, vector<int>& waterDuration) {
int n = (int)landStartTime.size(), m = (int)waterStartTime.size();
/* 合併開始、經過時刻，組成 (開始時刻, 經過時間) */
vector<pair<int, int>> land (n), water (m);
for(int i=0; i<n; i++) {
land[i].first = landStartTime[i];
land[i].second = landDuration[i];
}
for(int i=0; i<m; i++) {
water[i].first = waterStartTime[i];
water[i].second = waterDuration[i];
}
sort(land.begin(), land.end()); // 依照開始時刻排序
sort(water.begin(), water.end());
/* 取出排序後的開始時刻，用於二分搜尋法 */
vector<int> landStartSorted (n), waterStartSorted (m);
landStartSorted[0] = land[0].first;
waterStartSorted[0] = water[0].first;
/* 前綴最短持續時間 */
vector<int> landDurationMin (n, 0), waterDurationMin (m, 0);
landDurationMin[0] = land[0].second;
waterDurationMin[0] = water[0].second;
for(int i=1; i<n; i++) {
landStartSorted[i] = land[i].first;
landDurationMin[i] = min(landDurationMin[i-1], land[i].second);
}
for(int i=1; i<m; i++) {
waterStartSorted[i] = water[i].first;
waterDurationMin[i] = min(waterDurationMin[i-1], water[i].second);
}
/* 後綴最早結束時刻 */
vector<int> landFinishMin(n, 0), waterFinishMin (m, 0);
landFinishMin[n-1] = land[n-1].first + land[n-1].second;
waterFinishMin[m-1] = water[m-1].first + water[m-1].second;
for(int i=n-2; i>=0; i--) {
landFinishMin[i] = min(landFinishMin[i+1], land[i].first + land[i].second);
}
for(int i=m-2; i>=0; i--) {
waterFinishMin[i] = min(waterFinishMin[i+1], water[i].first + water[i].second);
}
/* 先去 land 再去 water 的最早結束時刻 */
int ans = 1000000000;
for(auto it : land) {
int landF = it.first + it.second, currMin = 1000000000;
/* 用二分搜尋法從 waterStart 之中找分界點 idx
idx 左側，已開放，可以直接玩
idx 右側，尚未開放，要等一段時間 */
auto idx = upper_bound(waterStartSorted.begin(), waterStartSorted.end(), landF) - waterStartSorted.begin();
// 狀況1，可以直接玩已開放的設施，取 landF 加上 0 ~ idx-1 最短持續時間
if (idx > 0) {
currMin = min(currMin, landF + waterDurationMin[idx - 1]);
}
// 狀況2，等待還沒有開放的設施，取 idx ~ m-1 最早結束時刻
if (idx < m) {
currMin = min(currMin, waterFinishMin[idx]);
}
ans = min(ans, currMin);
}
/* 先去 water 再去 land 的最早結束時刻 */
for(auto it : water) {
int waterF = it.first + it.second, currMin = 1000000000;
/* 用二分搜尋法從 landStart 之中找分界點 idx
idx 左側，已開放，可以直接玩
idx 右側，尚未開放，要等一段時間 */
auto idx = upper_bound(landStartSorted.begin(), landStartSorted.end(), waterF) - landStartSorted.begin();
// 狀況1，可以直接玩已開放的設施，取 waterF 加上 0 ~ idx-1 最短持續時間
if (idx > 0) {
currMin = min(currMin, waterF + landDurationMin[idx - 1]);
}
// 狀況2，等待還沒有開放的設施，取 idx ~ n-1 最早結束時刻
if (idx < n) {
currMin = min(currMin, landFinishMin[idx]);
}
ans = min(ans, currMin);
}
return ans;
}
};
沒有留言:
張貼留言