Watch 5 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 CodeWithMeGuys has 239 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two categories of theme park attractions: land rides and water rides.
landStartTime[i] – the earliest time the ith land ride can be boarded.landDuration[i] – how long the ith land ride lasts.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.
t, it finishes at time t + duration.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:
landStartTime[0] = 2. Finish at 2 + landDuration[0] = 6.waterStartTime[0] = 6. Start immediately at 6, finish at 6 + waterDuration[0] = 9.waterStartTime[0] = 6. Finish at 6 + waterDuration[0] = 9.landStartTime[1] = 8. Start at time 9, finish at 9 + landDuration[1] = 10.landStartTime[1] = 8. Finish at 8 + landDuration[1] = 9.waterStartTime[0] = 6. Start at time 9, finish at 9 + waterDuration[0] = 12.waterStartTime[0] = 6. Finish at 6 + waterDuration[0] = 9.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:
waterStartTime[0] = 1. Finish at 1 + waterDuration[0] = 11.landStartTime[0] = 5. Start immediately at 11 and finish at 11 + landDuration[0] = 14.landStartTime[0] = 5. Finish at 5 + landDuration[0] = 8.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 * 104landStartTime.length == landDuration.length == nwaterStartTime.length == waterDuration.length == m1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 105Problem 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.
| 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 |