Earliest Finish Time for Land and Water Rides II - Video Solutions
Earliest Finish Time for Land and Water Rides I and II | Story To Code | Leetcode 3633 & 3635 | MIK
Earliest Finish Time for Land and Water Rides II - Video Solution
Watch 10 video solutions for Earliest Finish Time for Land and Water Rides II, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by codestorywithMIK has 8,928 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given two categories of theme park attractions: land rides and water rides.
- Land rides
landStartTime[i]– the earliest time theithland ride can be boarded.landDuration[i]– how long theithland ride lasts.
- Water rides
waterStartTime[j]– the earliest time thejthwater ride can be boarded.waterDuration[j]– how long thejthwater 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 timet + 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 at2 + landDuration[0] = 6. - Water ride 0 opens at time
waterStartTime[0] = 6. Start immediately at6, finish at6 + waterDuration[0] = 9.
- Start land ride 0 at time
- Plan B (water ride 0 → land ride 1):
- Start water ride 0 at time
waterStartTime[0] = 6. Finish at6 + waterDuration[0] = 9. - Land ride 1 opens at
landStartTime[1] = 8. Start at time9, finish at9 + landDuration[1] = 10.
- Start water ride 0 at time
- Plan C (land ride 1 → water ride 0):
- Start land ride 1 at time
landStartTime[1] = 8. Finish at8 + landDuration[1] = 9. - Water ride 0 opened at
waterStartTime[0] = 6. Start at time9, finish at9 + waterDuration[0] = 12.
- Start land ride 1 at time
- Plan D (water ride 0 → land ride 0):
- Start water ride 0 at time
waterStartTime[0] = 6. Finish at6 + waterDuration[0] = 9. - Land ride 0 opened at
landStartTime[0] = 2. Start at time9, finish at9 + landDuration[0] = 13.
- Start water ride 0 at time
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 at1 + waterDuration[0] = 11. - Land ride 0 opened at
landStartTime[0] = 5. Start immediately at11and finish at11 + landDuration[0] = 14.
- Start water ride 0 at time
- Plan B (land ride 0 → water ride 0):
- Start land ride 0 at time
landStartTime[0] = 5. Finish at5 + landDuration[0] = 8. - Water ride 0 opened at
waterStartTime[0] = 1. Start immediately at8and finish at8 + waterDuration[0] = 18.
- Start land ride 0 at time
Plan A provides the earliest finish time of 14.āāāāāāā
Constraints:
1 <= n, m <= 5 * 104landStartTime.length == landDuration.length == nwaterStartTime.length == waterDuration.length == m1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 105
Approach Overview
Problem Overview: You are given two sets of rides: land rides and water rides. Each ride has a start time and duration. You must take exactly one land ride followed by one water ride. The goal is to choose a pair that finishes as early as possible while respecting the constraint that the water ride can only start after the land ride finishes.
Approach 1: Brute Force Pair Enumeration (O(n * m) time, O(1) space)
Check every possible pair of rides. For each land ride, compute its finish time using finish = start + duration. Then iterate over every water ride and see if its start time is valid. The final finish time becomes waterStart + waterDuration. Track the minimum across all valid combinations. This approach is straightforward but inefficient because it evaluates all pairs, which becomes expensive when both ride lists are large.
Approach 2: Enumeration + Greedy with Sorting (O(n log n + m log m) time, O(1) extra space)
Sort water rides by start time. Then iterate through each land ride and compute its finish time. Instead of checking all water rides, use binary search to find the earliest water ride whose start time is greater than or equal to the land finish time. Because the rides are sorted, this gives the earliest feasible second ride immediately. Compute the resulting finish time and update the global minimum. Sorting combined with greedy selection removes unnecessary comparisons.
Approach 3: Two Pointers After Sorting (O(n log n + m log m) time, O(1) space)
Sort both land and water rides by start time. Traverse land rides in increasing order of finish time while advancing a pointer through the sorted water rides to maintain the earliest feasible candidate. This uses the monotonic property of sorted arrays and avoids repeated binary searches. The technique resembles classic scheduling problems that rely on greedy pairing and sequential scans over sorted arrays.
Recommended for interviews: Enumeration combined with sorting and binary search is typically expected. The brute force approach shows understanding of the constraints, but the optimized greedy pairing demonstrates algorithmic maturity and reduces the search from quadratic to near-linear after sorting.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Enumeration | O(n * m) | O(1) | Small input sizes or initial baseline solution during interviews |
| Sorting + Binary Search (Greedy Pairing) | O(n log n + m log m) | O(1) | General optimal solution when rides must be paired with start-time constraints |
| Two Pointers After Sorting | O(n log n + m log m) | O(1) | When arrays are sorted and you want to avoid repeated binary searches |