3635. Earliest Finish Time for Land and Water Rides II

題目 / Problem

中文： 遊樂園裡有兩類設施：陸上設施 (land rides) 和 水上設施 (water rides)。

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

遊客必須從每一類各玩一個（恰好一個陸上、一個水上），順序任意（可以先陸後水，也可以先水後陸）。 規則：設施可以在它的開放時間或之後任何時刻開始；若在時間 t 開始，會在 t + duration 結束；玩完一個之後，若另一個已開放就可立刻開始，否則要等到它開放。 求最早能玩完兩個設施的時間。

English: A theme park has two categories of attractions: land rides and water rides.

• Land ride i: landStartTime[i] is the earliest boarding time, landDuration[i] is how long it lasts.
• Water ride j: waterStartTime[j] is the earliest boarding time, waterDuration[j] is its length.

A tourist must take exactly one ride from each category, in either order. A ride can begin at its opening time or any later moment; starting at time t means finishing at t + duration. After finishing one ride, the tourist boards the other immediately if it is already open, otherwise waits until it opens. Return the earliest possible time to finish both rides.

Constraints / 限制： - 1 <= n, m <= 5 * 10^4 - landStartTime.length == landDuration.length == n - waterStartTime.length == waterDuration.length == m - 1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 10^5

Worked example / 範例： landStartTime = [2,8], landDuration = [4,1], waterStartTime = [6], waterDuration = [3] → Output 9. 先玩陸上設施 0（時間 2 開始，6 結束），水上設施 0 在時間 6 開放，立刻開始，9 結束。

名詞解釋 / Glossary

• finish time / 結束時間：一個設施的結束時間 = 開始時間 + 持續時間。若在開放時間就立刻開始，最早結束時間 = startTime + duration。
• greedy / 貪心法：每一步都選當下看起來最好的選擇，並能證明這樣會得到全域最優解。本題中「第一個設施一定選最早結束的那個」就是貪心。
• max(a, b) / 取較大值：等待邏輯的核心。第二個設施的真正開始時間 = max(我玩完第一個的時間, 第二個的開放時間)——兩者誰晚就以誰為準（要嘛我還沒玩完、要嘛它還沒開）。
• O(n + m) / 線性時間：演算法的步數與資料量成正比，這裡只需把兩個陣列各掃幾遍，不需排序或巢狀迴圈。

思路

最直覺的暴力法是：列舉每一個陸上設施 i 配上每一個水上設施 j，再分別算「先陸後水」與「先水後陸」兩種順序的結束時間，取全部之中的最小值。但這樣是 O(n × m)，當 n 和 m 都到 5 × 10^4 時會達到約 25 億次運算，太慢了。

關鍵的觀察是：當順序固定時，第一個玩的設施一定要選「最早結束」的那一個。為什麼?假設順序是「先陸後水」,設第一個陸上設施結束於時間 L。那麼水上設施 j 的結束時間是 max(L, waterStart[j]) + waterDuration[j]。這個式子對 L 是「不減的」——L 越小,max(...) 不會變大,結束時間也不會變大。所以對任何水上設施 j 來說,讓 L 越小都越好,因此第一個陸上設施只要取「start + duration 最小」的那個即可,完全不必逐一列舉。同理「先水後陸」也是如此。於是演算法變成:先算出陸上最早結束時間 minLandFinish 與水上最早結束時間 minWaterFinish;對「先陸後水」掃一遍所有水上設施求 max(minLandFinish, waterStart[j]) + waterDuration[j] 的最小值;對「先水後陸」掃一遍所有陸上設施;兩種順序的答案再取最小。整體只需線性時間。

The brute force enumerates every land ride i paired with every water ride j, computing both orderings — that is O(n × m), around 2.5 billion operations at the limits, far too slow. The crucial insight is that for a fixed ordering, the first ride should always be the one that finishes earliest. Suppose we go land-then-water and the first land ride finishes at time L. Then water ride j finishes at max(L, waterStart[j]) + waterDuration[j], which is monotonically non-decreasing in L — a smaller L never hurts and often helps, for every j. So the best first land ride is simply the one minimizing start + duration; we never need to try the others. The same holds for water-then-land. The algorithm therefore reduces to: compute minLandFinish and minWaterFinish (the earliest finish in each category); for land-then-water, scan all water rides taking min(max(minLandFinish, waterStart[j]) + waterDuration[j]); for water-then-land, scan all land rides symmetrically; return the smaller of the two orderings. This runs in linear time with constant extra space.

逐步走查 / Walkthrough

Example: landStartTime = [2,8], landDuration = [4,1], waterStartTime = [6], waterDuration = [3].

Step 1 — 算各設施最早結束時間 / earliest finish of each ride

• minLandFinish = min(6, 9) = 6
• minWaterFinish = min(9) = 9

Step 2 — 先陸後水 / land then water （第一個用 minLandFinish = 6）

→ ans1 = 9

Step 3 — 先水後陸 / water then land （第一個用 minWaterFinish = 9）

→ ans2 = min(13, 10) = 10

Step 4 — 取最小 / take the minimum answer = min(ans1, ans2) = min(9, 10) = 9 ✅

Solution — C

/*
 * 演算法 / Algorithm:
 * 1) 先各自找出最早結束的設施 (start+duration 最小者)。
 *    Find the earliest-finishing ride in each category.
 * 2) 第一個設施固定用最早結束的那個（貪心 / greedy），
 *    再掃另一類，第二個設施開始於 max(firstFinish, otherStart)。
 * 3) 兩種順序各算一次，取最小。Try both orders, take the min.
 */

// 小工具：回傳兩數中較大者 / helper: returns the larger of two ints
static int maxInt(int a, int b) {
    return a > b ? a : b;   // 三元運算子：a>b 成立回 a，否則回 b / ternary operator
}

int earliestFinishTime(int* landStartTime, int landStartTimeSize,
                       int* landDuration, int landDurationSize,
                       int* waterStartTime, int waterStartTimeSize,
                       int* waterDuration, int waterDurationSize) {
    // 先把陸上「最早結束時間」算出來 / earliest finish among land rides
    int minLandFinish = landStartTime[0] + landDuration[0];        // 用第 0 個當初始值 / seed with ride 0
    for (int i = 1; i < landStartTimeSize; i++) {                   // 從第 1 個開始掃 / scan the rest
        int finish = landStartTime[i] + landDuration[i];           // 此設施最早結束 / this ride's finish
        if (finish < minLandFinish) minLandFinish = finish;        // 更新最小值 / keep the smallest
    }

    // 同理算出水上「最早結束時間」/ likewise the earliest water finish
    int minWaterFinish = waterStartTime[0] + waterDuration[0];     // 初始值 / seed
    for (int j = 1; j < waterStartTimeSize; j++) {
        int finish = waterStartTime[j] + waterDuration[j];
        if (finish < minWaterFinish) minWaterFinish = finish;
    }

    // 順序一：先陸後水 / order 1: land then water
    // 第一個固定 minLandFinish，第二個（水上）開始於 max(minLandFinish, 水上開放時間)
    // first ride fixed at minLandFinish; water starts at max(minLandFinish, its open time)
    int best = -1;                                                  // -1 代表還沒填值 / "not set yet"
    for (int j = 0; j < waterStartTimeSize; j++) {
        // 等待邏輯：誰晚就從誰開始 / wait until both "done first ride" and "open"
        int finish = maxInt(minLandFinish, waterStartTime[j]) + waterDuration[j];
        if (best == -1 || finish < best) best = finish;            // 第一次或更小就更新 / update min
    }

    // 順序二：先水後陸 / order 2: water then land
    for (int i = 0; i < landStartTimeSize; i++) {
        int finish = maxInt(minWaterFinish, landStartTime[i]) + landDuration[i];
        if (finish < best) best = finish;                          // 與順序一一起取全域最小 / global min
    }

    return best;   // 兩種順序中最早完成的時間 / earliest finish over both orders
}

Solution — C++

/*
 * 演算法 / Algorithm:
 * 第一個設施貪心地取「最早結束」者；第二個設施開始於
 * max(第一個結束時間, 第二個開放時間)。兩種順序各算一次取最小。
 * Greedily fix the first ride as the earliest-finishing one; the second
 * starts at max(first finish, its open time). Try both orders, take the min.
 */
#include <vector>
#include <algorithm>   // 提供 std::min / std::max / provides std::min, std::max
using namespace std;

class Solution {
public:
    int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration,
                           vector<int>& waterStartTime, vector<int>& waterDuration) {
        // lambda：傳入 start、duration 兩個陣列，回傳「最早結束時間」
        // a lambda (inline function) returning the earliest start+duration over a category
        auto earliestFinish = [](const vector<int>& start, const vector<int>& dur) {
            int best = start[0] + dur[0];                  // 用第 0 個當初始 / seed with index 0
            for (size_t k = 1; k < start.size(); k++)      // size_t 是無號整數，常用於索引 / unsigned index type
                best = min(best, start[k] + dur[k]);       // std::min 取較小者 / keep the smallest
            return best;
        };

        int minLandFinish  = earliestFinish(landStartTime,  landDuration);   // 陸上最早結束 / earliest land finish
        int minWaterFinish = earliestFinish(waterStartTime, waterDuration);  // 水上最早結束 / earliest water finish

        int best = INT_MAX;   // 先設成極大值，方便後面取 min / start at "infinity" so any real value wins

        // 順序一：先陸後水 / order 1: land then water
        for (size_t j = 0; j < waterStartTime.size(); j++) {
            // 第二個設施真正開始時間 = max(已玩完第一個的時間, 它的開放時間)
            // the second ride actually starts at max(first-finish, its own open time)
            int finish = max(minLandFinish, waterStartTime[j]) + waterDuration[j];
            best = min(best, finish);                       // 更新全域最小 / update the running minimum
        }

        // 順序二：先水後陸 / order 2: water then land
        for (size_t i = 0; i < landStartTime.size(); i++) {
            int finish = max(minWaterFinish, landStartTime[i]) + landDuration[i];
            best = min(best, finish);
        }

        return best;   // 最早完成兩個設施的時間 / earliest time to finish both
    }
};

複雜度 / Complexity

• Time: O(n + m) — n 是陸上設施數、m 是水上設施數。我們只各掃陣列常數次（找最早結束各一遍、兩種順序各一遍），沒有巢狀迴圈。We make a constant number of linear passes over each array; no nested loops, so the work is proportional to the total number of rides.
• Space: O(1) — 只用了 minLandFinish、minWaterFinish、best 等幾個變數，與輸入大小無關。Only a handful of scalar variables are used, independent of input size.

Pitfalls & Edge Cases

• 誤以為要列舉所有 i×j 配對 / thinking you must enumerate all i×j pairs：那是 O(n·m)，在大輸入會超時。關鍵是第一個設施只需取「最早結束」那個即可，因為更早結束永遠不會更糟。The brute-force pairing times out; the greedy "earliest first ride" collapses it to linear.
• 忘記等待邏輯用 max / forgetting the max for waiting：第二個設施的開始時間是 max(第一個結束, 第二個開放)，不能直接相加。若漏掉 max，當第二個設施還沒開放時會算出不可能的太早時間。You must wait for the later of the two; dropping max gives an impossible early start.
• 兩種順序都要試 / both orders matter：先陸後水和先水後陸結果可能不同（見範例 2，答案 14 來自先水後陸），只算一種會答錯。Example 2's answer comes from water-then-land; checking only one order is wrong.
• 初始值設定 / initializing the running minimum：C 用 -1 旗標、C++ 用 INT_MAX，避免把「還沒比較」的狀態誤當成真實答案。Seed the minimum carefully so the first comparison is valid.
• 不會溢位 / no overflow：start, duration <= 10^5，相加最多約 2×10^5，遠在 32 位元 int 範圍內，無需 long。Values stay well within int.