LeetCode Problem Workspace
Earliest Finish Time for Land and Water Rides II
Determine the minimum completion time for a tourist to ride one land and one water ride using optimal scheduling.
0
Topics
5
Code langs
0
Related
Practice Focus
Medium · Earliest Finish Time for Land and Water Rides II core interview pattern
Answer-first summary
Determine the minimum completion time for a tourist to ride one land and one water ride using optimal scheduling.
Ace coding interviews with Interview AiBoxInterview AiBox guidance for Earliest Finish Time for Land and Water Rides II core interview pattern
Start by sorting land and water rides by their start times. Use prefix minimums for durations and suffix minimums for finish times to quickly identify optimal ride combinations. This ensures you calculate the earliest possible time to finish both rides while handling multiple rides efficiently.
Problem Statement
You are at a theme park with two ride types: land rides and water rides. Each ride has a start time and duration. A tourist wants to take exactly one ride from each type, in any order, and finish both as early as possible.
Given arrays representing the start times and durations for each land and water ride, compute the earliest overall finish time for completing one ride of each type. Consider all possible sequences and overlap scenarios to find the minimum total finish time.
Examples
Example 1
Input: landStartTime = [2,8], landDuration = [4,1], waterStartTime = [6], waterDuration = [3]
Output: 9
Plan A gives the earliest finish time of 9.
Example 2
Input: landStartTime = [5], landDuration = [3], waterStartTime = [1], waterDuration = [10]
Output: 14
Plan A provides the earliest finish time of 14.
Constraints
- 1 <= n, m <= 5 * 104
- landStartTime.length == landDuration.length == n
- waterStartTime.length == waterDuration.length == m
- 1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 105
Solution Approach
Sort rides by start time
Sort both land and water rides by their start times. This allows sequential scanning to find optimal ride pairings without checking all combinations explicitly.
Use prefix and suffix minimums
Build a prefix minimum array of durations for the first ride type and a suffix minimum array of finish times for the second ride type. This efficiently identifies the earliest possible finish time for any given first ride selection.
Compute minimum combined finish
Iterate through the sorted rides using the prefix and suffix arrays to calculate the combined finish time for each possible order. Return the smallest value, representing the earliest completion for one land and one water ride.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n log n + m log m) due to sorting and linear scanning for prefix/suffix computations. Space complexity is O(n + m) for storing prefix and suffix arrays.
What Interviewers Usually Probe
- Checks if you can identify that sorting and prefix/suffix arrays reduce brute force pairing.
- Looks for correct handling of ride order permutations to minimize total finish time.
- Wants efficient computation under large input constraints rather than naive nested loops.
Common Pitfalls or Variants
Common pitfalls
- Failing to consider both ride order possibilities can give a suboptimal finish time.
- Not using prefix/suffix minimums may result in timeouts for large input sizes.
- Mixing start times and finish times incorrectly when combining rides leads to wrong results.
Follow-up variants
- Compute earliest finish for multiple rides of each type while allowing repeated rides.
- Extend to k ride categories with the same earliest finish pattern.
- Allow skipping certain rides if their durations exceed a threshold while minimizing total finish time.
FAQ
What is the core pattern in Earliest Finish Time for Land and Water Rides II?
The problem centers on selecting one ride from each type to minimize total finish time, using sorting and prefix/suffix minimum arrays.
Can I process rides in any order?
Yes, but both sequences must be considered; the optimal finish depends on the order and ride durations.
How do prefix and suffix arrays help?
They allow O(1) lookup of the minimal finish time for remaining rides, reducing brute-force computation.
What is the time complexity for this approach?
Sorting takes O(n log n + m log m), and scanning for prefix/suffix minimums is O(n + m), giving overall efficient computation.
What happens with overlapping start times?
The algorithm handles overlaps by considering both ride orders and calculating finish times using prefix and suffix arrays to ensure minimal total time.
Solution
Solution 1: Enumeration + Greedy
We can consider two orders of rides: first land rides then water rides, or first water rides then land rides.
class Solution:
def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
def calc(a1, t1, a2, t2):
min_end = min(a + t for a, t in zip(a1, t1))
return min(max(a, min_end) + t for a, t in zip(a2, t2))
x = calc(landStartTime, landDuration, waterStartTime, waterDuration)
y = calc(waterStartTime, waterDuration, landStartTime, landDuration)
return min(x, y)