Finish a Land and Water Ride from Large Lists

# Finish a Land and Water Ride from Large Lists A visitor must choose exactly one land ride and exactly one water ride, and complete them sequentially in either order. The land rides are described by `landStartTime` and `landDuration`: ride `i` opens at `landStartTime[i]` and lasts `landDuration[i]`. The corresponding arrays `waterStartTime` and `waterDuration` describe the water rides. The visitor may begin a ride at its opening time or any later time. A ride beginning at time `t` ends at `t + duration`. After the first ride ends, the visitor can board the other ride immediately if it is open, or wait for it to open. Return the earliest possible completion time for both rides. ### C++ Interface ```cpp class Solution { public: int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration, vector<int>& waterStartTime, vector<int>& waterDuration) { } }; ``` ### Examples **Example 1** **Input:** `landStartTime = [4, 13, 8], landDuration = [6, 1, 3], waterStartTime = [9, 2], waterDuration = [2, 7]` **Output:** `12` **Explanation:** Take land ride `0` from `4` to `10`, then water ride `0` from `10` to `12`. Another optimal plan takes water ride `1` from `2` to `9`, then land ride `2` from `9` to `12`. Both satisfy the opening times, and no valid plan finishes earlier. **Example 2** **Input:** `landStartTime = [100000], landDuration = [100000], waterStartTime = [1, 99999], waterDuration = [100000, 1]` **Output:** `200000` **Explanation:** Take water ride `1` from `99999` to `100000`, then the land ride from `100000` to `200000`. The land ride alone cannot end before `200000`, so this plan is optimal. ### Constraints - `1 <= n, m <= 50000` - `landStartTime.length == landDuration.length == n` - `waterStartTime.length == waterDuration.length == m` - `1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 100000` ### Clarifying Questions - Do matching indices across the two categories describe a pair? No; any land ride may be chosen with any water ride. - Are opening times compulsory start times? No; a ride may be boarded later. - Is there a transfer delay between rides? No; the second may start immediately when the first finishes, provided it is open. - Are the input lists ordered? No ordering is promised. ### What a Strong Answer Covers - An attainable earliest completion time for exactly one ride from each category. - Correct treatment of waiting, unequal list sizes, and tied completion times. - A justified time and space bound suitable for lists of up to 50000 rides. ### Follow-up Questions - If chosen ride indices must also be returned, what should the contract say about ties? - How would a fixed transfer delay between categories change the scheduling rules? ```hint An earlier first completion Fix the category taken first. If one choice finishes that first ride earlier than another, can it ever force a later completion for a specified second ride? Use that comparison to reduce the number of first-ride choices you need to retain. ```