You are given two categories of theme park attractions: land rides and water rides.
Land rides
landStartTime[i] – the earliest time the ith land ride can be boarded.
landDuration[i] – how long the ith land ride lasts.
Water rides
waterStartTime[j] – the earliest time the jth water ride can be boarded.
waterDuration[j] – how long the jth water ride lasts.
A tourist must experience exactly one ride from each category, in either order.
A ride may be started at its opening time or any later moment.
If a ride is started at time t, it finishes at time t + duration.
Immediately after finishing one ride the tourist may board the other (if it is already open) or wait until it opens.
Return the earliest possible time at which the tourist can finish both rides.
Example 1:
Input: landStartTime = [2,8], landDuration = [4,1], waterStartTime = [6], waterDuration = [3]
Output: 9
Explanation:
Plan A (land ride 0 → water ride 0):
Start land ride 0 at time landStartTime[0] = 2. Finish at 2 + landDuration[0] = 6.
Water ride 0 opens at time waterStartTime[0] = 6. Start immediately at 6, finish at 6 + waterDuration[0] = 9.
Plan B (water ride 0 → land ride 1):
Start water ride 0 at time waterStartTime[0] = 6. Finish at 6 + waterDuration[0] = 9.
Land ride 1 opens at landStartTime[1] = 8. Start at time 9, finish at 9 + landDuration[1] = 10.
Plan C (land ride 1 → water ride 0):
Start land ride 1 at time landStartTime[1] = 8. Finish at 8 + landDuration[1] = 9.
Water ride 0 opened at waterStartTime[0] = 6. Start at time 9, finish at 9 + waterDuration[0] = 12.
Plan D (water ride 0 → land ride 0):
Start water ride 0 at time waterStartTime[0] = 6. Finish at 6 + waterDuration[0] = 9.
Land ride 0 opened at landStartTime[0] = 2. Start at time 9, finish at 9 + landDuration[0] = 13.
Plan A gives the earliest finish time of 9.
Example 2:
Input: landStartTime = [5], landDuration = [3], waterStartTime = [1], waterDuration = [10]
Output: 14
Explanation:
Plan A (water ride 0 → land ride 0):
Start water ride 0 at time waterStartTime[0] = 1. Finish at 1 + waterDuration[0] = 11.
Land ride 0 opened at landStartTime[0] = 5. Start immediately at 11 and finish at 11 + landDuration[0] = 14.
Plan B (land ride 0 → water ride 0):
Start land ride 0 at time landStartTime[0] = 5. Finish at 5 + landDuration[0] = 8.
Water ride 0 opened at waterStartTime[0] = 1. Start immediately at 8 and finish at 8 + waterDuration[0] = 18.
Plan A provides the earliest finish time of 14.
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
這題是明天的 Daily，題目敘述跟今天的一樣，
只是計算複雜度要求的比較嚴格。
題目給我們四個陣列，
分別代表陸上、水上遊樂設施的啟動時間與持續時間。
題目希望我們得到客人可以最早玩過兩個設施各一次的時間點。
假設陸上水上啟動陣列的長度分別是 M, N，
用暴力配對的計算複雜度是 O(MN)。
但這樣實在是太醜了，我今天就想了一下，
原本是想把啟動陣列與持續時間做計算，每個時間點都做當前最佳像是：
StartTime = [1, 2, 3], Duration = [4, 5, 6]，
這樣去求結束時間陣列 [5, 7, 9]，然後再對另一個遊樂設施做配對，
但這樣計算起來也是 O(MN)，因為有起始時間限制，除非做 0 ~ K時間段，不然用事件是做不了當前最佳，做 0 ~ K 的話又因為稀疏事件戳記，會佔用太多記憶體。
所以想了一下，用兩邊最早可以結束的時間戳記相互配對，
有想過會不會次早結束的時間會配對到另一個次早時間，
但是不會，因為結束時間戳記是單項遞增的，
而且互相配對後已經考慮陸上設施在前以及水上設施在前的問題。
C++程式碼：
