3633. Earliest Finish Time for Land and Water Rides I

題目 / Problem

你在一座主題樂園，有兩類設施：陸上設施（land rides） 和 水上設施（water rides）。

• 第 i 個陸上設施：landStartTime[i] 是它最早可以上的時間，landDuration[i] 是它持續多久。
• 第 j 個水上設施：waterStartTime[j] 是它最早可以上的時間，waterDuration[j] 是它持續多久。

遊客必須從每一類各玩剛好一個設施，順序自由（可以先陸後水，也可以先水後陸）。設施可以在開放時間或之後任何時刻開始；若在時間 t 開始，會在 t + duration 結束。玩完一個之後可以馬上去玩另一個（如果它已經開放），否則要等到它開放。請回傳最早能玩完兩個設施的時間。

You are at a theme park with two categories of rides: land rides and water rides. For land ride i, landStartTime[i] is the earliest boarding time and landDuration[i] is its length; water rides are defined the same way with waterStartTime[j] and waterDuration[j]. A tourist must take exactly one ride from each category, in either order. A ride started at time t finishes at t + duration, and may begin no earlier than its opening time. After finishing one ride you may board the other immediately if it is already open, or wait until it opens. Return the earliest time both rides can be finished.

Constraints / 限制 - 1 <= n, m <= 100 - landStartTime.length == landDuration.length == n - waterStartTime.length == waterDuration.length == m - 1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 1000

Example / 範例

landStartTime = [2,8], landDuration = [4,1], waterStartTime = [6], waterDuration = [3]
Output: 9

最佳方案：先玩陸上設施 0（2 點開始，6 點結束），再玩水上設施 0（6 點開放，馬上開始，9 點結束）。/ Best plan: land ride 0 from 2 to 6, then water ride 0 starting at 6 and finishing at 9.

名詞解釋 / Glossary

• 暴力枚舉 / Brute force：把所有可能的組合一個一個試過去，從中挑最好的答案。這題的組合數很小，所以這招完全夠用。/ Try every possible combination one by one and keep the best answer. The number of combinations here is tiny, so this is more than fast enough.
• 持續時間 / Duration：一個設施從開始到結束所花的時間。開始時間加上持續時間就是結束時間。/ How long a ride takes from start to finish; start time plus duration equals finish time.
• 等待 / Waiting：玩完第一個設施後，第二個設施可能還沒開放，這時必須等到它的開放時間才能開始。我們用 max(到達時間, 開放時間) 來表示「不能比開放時間早開始」。/ After the first ride you might arrive before the second ride opens, so you must wait. We model this with max(arrival time, opening time) — you can't start before it opens.
• max 函式 / The max function：回傳兩個數中較大的那一個。這裡用來處理「至少要等到開放時間」。/ Returns the larger of two numbers; used here to enforce "no earlier than the opening time."

思路

這題其實只需要暴力枚舉。我們要從陸上設施挑一個、水上設施挑一個，而且兩個的順序可以交換，所以對每一對 (i, j) 都有兩種玩法。第一種是「先陸後水」：先玩第 i 個陸上設施，它在 landStartTime[i] + landDuration[i] 結束；接著去玩第 j 個水上設施，但不能比它的開放時間早開始，所以開始時間是 max(陸上結束時間, waterStartTime[j])，結束時間再加上 waterDuration[j]。第二種是「先水後陸」，把角色對調即可。對每一對組合，取這兩種玩法中較早結束的，再對所有組合取全域最小值，就是答案。

為什麼這樣是對的？因為總共只有 n × m 對組合，而每對只有兩種順序，全部加起來最多 100 × 100 × 2 = 20000 種情況，電腦瞬間就能算完，完全不需要更聰明的演算法。關鍵的觀念是「等待」：玩完第一個設施時，第二個設施不一定開放了，所以第二個的開始時間必須是「我到達的時間」和「它的開放時間」之中比較晚的那一個，這就是用 max 的原因。只要每一對、每一種順序都算對，再保留最小值，就保證找到最早完成時間。

This problem only needs brute force. We must pick one land ride and one water ride, and since the two can be done in either order, every pair (i, j) gives two plans. Plan one is land-then-water: finish the land ride at landStartTime[i] + landDuration[i], then start the water ride no earlier than its opening time, so it starts at max(land finish, waterStartTime[j]) and finishes after adding waterDuration[j]. Plan two is water-then-land, with the roles swapped. For each pair we take the better of the two orders, then take the global minimum across all pairs — that is the answer.

Why is this correct and fast enough? There are only n × m pairs, each with two orderings, so at most 100 × 100 × 2 = 20000 cases — instant for a computer, no cleverer algorithm needed. The key idea is the waiting step: when you finish the first ride, the second may not be open yet, so its start time must be the later of "when I arrive" and "when it opens," which is exactly what max captures. As long as every pair and every order is computed correctly and we keep the minimum, we are guaranteed to find the earliest finish time.

逐步走查 / Walkthrough

用範例 1：landStartTime = [2,8], landDuration = [4,1], waterStartTime = [6], waterDuration = [3]。只有一個水上設施（j = 0），兩個陸上設施。我們把 ans 初始化成一個很大的數。

走查完所有組合後，ans = 9，這就是答案。/ After scanning all pairs, ans = 9, which is the answer.

Solution — C

// 演算法：暴力枚舉每一對 (陸上 i, 水上 j)，兩種順序都算，取最早結束時間。
// Algorithm: brute-force every (land i, water j) pair, try both orders,
// and keep the earliest finish time. n*m pairs is tiny, so this is fast enough.

// LeetCode 會把陣列和它們的長度一起傳進來 / LeetCode passes each array with its length.
int earliestFinishTime(int* landStartTime, int landStartTimeSize,
                       int* landDuration, int landDurationSize,
                       int* waterStartTime, int waterStartTimeSize,
                       int* waterDuration, int waterDurationSize) {
    int ans = 2147483647;  // 先設成 int 最大值，之後不斷取較小 / start at INT_MAX, then keep shrinking

    // 外層跑每一個陸上設施 / outer loop over every land ride
    for (int i = 0; i < landStartTimeSize; i++) {
        // 內層跑每一個水上設施 / inner loop over every water ride
        for (int j = 0; j < waterStartTimeSize; j++) {

            // 先陸後水：陸上設施的結束時間 / land first: when the land ride finishes
            int landFinish = landStartTime[i] + landDuration[i];
            // 水上設施不能比開放時間早開始，所以取兩者較大的 / water can't start before it opens
            int startWater = landFinish > waterStartTime[j] ? landFinish : waterStartTime[j];
            int plan1 = startWater + waterDuration[j];  // 加上水上時長 = 整體結束 / add water duration

            // 先水後陸：水上設施的結束時間 / water first: when the water ride finishes
            int waterFinish = waterStartTime[j] + waterDuration[j];
            // 陸上設施同樣不能比它的開放時間早開始 / land likewise can't start before it opens
            int startLand = waterFinish > landStartTime[i] ? waterFinish : landStartTime[i];
            int plan2 = startLand + landDuration[i];    // 加上陸上時長 = 整體結束 / add land duration

            // 這一對的最佳順序 / better of the two orders for this pair
            int best = plan1 < plan2 ? plan1 : plan2;

            // 若比目前答案更早，就更新 / update the global minimum if this is earlier
            if (best < ans) ans = best;
        }
    }
    return ans;  // 全域最早完成時間 / the earliest finish time overall
}

Solution — C++

// 演算法：暴力枚舉每一對 (陸上, 水上)，兩種順序都試，回傳最小結束時間。
// Algorithm: brute-force every (land, water) pair, try both orders, return the min finish.
// n,m <= 100, so at most 20000 cases — trivially fast.

class Solution {
public:
    int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration,
                           vector<int>& waterStartTime, vector<int>& waterDuration) {
        int ans = INT_MAX;  // INT_MAX 是 int 能表示的最大值，當作初始上界 / largest int, used as initial upper bound

        // range-for 之外用傳統索引，因為要同時取 start 與 duration 兩個陣列的同一格
        // use index loops because we need the same index into both the start and duration arrays
        for (size_t i = 0; i < landStartTime.size(); ++i) {
            for (size_t j = 0; j < waterStartTime.size(); ++j) {

                // 先陸後水 / land first
                int landFinish = landStartTime[i] + landDuration[i];
                // std::max 回傳較大值：確保水上設施不早於開放時間開始 / max enforces the opening time
                int plan1 = max(landFinish, waterStartTime[j]) + waterDuration[j];

                // 先水後陸 / water first
                int waterFinish = waterStartTime[j] + waterDuration[j];
                int plan2 = max(waterFinish, landStartTime[i]) + landDuration[i];

                // 這一對取較早的順序，再更新全域最小值 / take the earlier order, then update the global min
                ans = min(ans, min(plan1, plan2));
            }
        }
        return ans;  // 最早完成時間 / earliest finish time
    }
};

複雜度 / Complexity

• Time: O(n × m) — 兩層迴圈，外層 n 個陸上設施、內層 m 個水上設施，每對做常數次運算。n, m ≤ 100，最多約一萬次，瞬間完成。/ Two nested loops over n land rides and m water rides, with constant work per pair. With n, m ≤ 100 that's ~10000 operations — instant.
• Space: O(1) — 只用了幾個整數變數，沒有額外配置陣列。/ Only a handful of integer variables; no extra arrays allocated.

Pitfalls & Edge Cases

• 忘記兩種順序 / Forgetting both orders：必須同時考慮「先陸後水」和「先水後陸」，因為哪個先做會影響等待時間。只算一種會漏掉更早的答案。/ You must try land-first and water-first; which one goes first changes the waiting time, so checking only one order can miss the earlier finish.
• 忘記等待（max）/ Forgetting the wait (max)：第二個設施的開始時間是「到達時間」和「開放時間」中較晚的。若直接用到達時間相加，當設施還沒開放時會算出不可能的時間。/ The second ride starts at the later of arrival time and opening time. Skipping the max would let a ride start before it opens, giving an impossible answer.
• ans 初始值 / Initial value of ans：必須設成夠大的數（INT_MAX），否則一開始就比所有真實答案小，最小值永遠不會被更新。/ Initialize ans to a large value (INT_MAX); otherwise it starts below real answers and never gets replaced.
• 不會溢位 / No overflow：所有值 ≤ 1000，最壞情況約 1000 + 1000 + 1000 = 3000，遠在 int 範圍內，不必擔心整數溢位。/ All values ≤ 1000, so the worst finish is around 3000 — well within int, so overflow is not a concern.