3635. Earliest Finish Time for Land and Water Rides II

MediumGreedyArrayTwo PointersBinary SearchSorting

Leetcode Link

Problem Description

You are visiting a theme park that has two types of attractions: land rides and water rides.

For each type of ride, you are given information about when they open and how long they last:

Land rides:

landStartTime[i] - the earliest time the i-th land ride can be boarded
landDuration[i] - how long the i-th land ride lasts

Water rides:

waterStartTime[j] - the earliest time the j-th water ride can be boarded
waterDuration[j] - how long the j-th water ride lasts

As a tourist, you must experience exactly one ride from each category. You can ride them in either order (land first then water, or water first then land).

The rules for riding are:

You can start a ride at its opening time or any time after it opens
If you start a ride at time t, you will finish at time t + duration
After finishing one ride, you can immediately board the next ride (if it's already open) or wait until it opens

Your goal is to find the earliest possible time at which you can finish both rides.

For example, if you choose to do a land ride first that opens at time 2 with duration 3, you'll finish at time 5. Then if you want to do a water ride that opens at time 4 with duration 2, you can board it immediately at time 5 (since it's already open) and finish at time 7. The total completion time would be 7.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

Since we need to ride exactly one attraction from each category, we have two possible orders: land ride first then water ride, or water ride first then land ride. We need to consider both orders and pick the one that finishes earliest.

For any given order, the key insight is that we want to minimize our total completion time. If we go with land rides first, we should pick the land ride that finishes earliest (minimizing waiting time for the water ride). This earliest finish time for the first ride becomes minEnd = min(startTime + duration) across all rides of that type.

Once we finish the first ride at time minEnd, we need to pick a water ride. For each possible water ride, we can board it at time max(minEnd, waterStartTime) - either right after finishing the land ride if the water ride is already open, or we wait until it opens. The total completion time would be max(minEnd, waterStartTime) + waterDuration.

To find the optimal solution for this order, we need to check all possible water rides and pick the one that gives us the earliest completion time: min(max(minEnd, waterStartTime[j]) + waterDuration[j]) for all j.

The same logic applies when we reverse the order (water rides first, then land rides).

The final answer is the minimum completion time between these two orders. This greedy approach works because once we commit to an order, choosing the earliest-finishing first ride gives the second ride the best chance to start early, and then we simply pick whichever second ride can finish earliest given that constraint.

Learn more about Greedy, Two Pointers, Binary Search and Sorting patterns.

Solution Implementation

1from typing import List 2 3class Solution: 4 def earliestFinishTime( 5 self, 6 landStartTime: List[int], 7 landDuration: List[int], 8 waterStartTime: List[int], 9 waterDuration: List[int], 10 ) -> int: 11 def calculate_finish_time( 12 first_start_times: List[int], 13 first_durations: List[int], 14 second_start_times: List[int], 15 second_durations: List[int] 16 ) -> int: 17 """ 18 Calculate the minimum finish time when completing first task then second task. 19 20 Args: 21 first_start_times: Start times for first set of tasks 22 first_durations: Durations for first set of tasks 23 second_start_times: Start times for second set of tasks 24 second_durations: Durations for second set of tasks 25 26 Returns: 27 Minimum possible finish time 28 """ 29 # Find the earliest possible completion time among all first tasks 30 min_first_task_end = min( 31 start + duration 32 for start, duration in zip(first_start_times, first_durations) 33 ) 34 35 # For each second task, calculate finish time considering: 36 # - Must start after first task completes (min_first_task_end) 37 # - Must respect the second task's own start time constraint 38 # Then find the minimum among all possible second tasks 39 return min( 40 max(start, min_first_task_end) + duration 41 for start, duration in zip(second_start_times, second_durations) 42 ) 43 44 # Try both orderings: land first then water, or water first then land 45 land_then_water = calculate_finish_time( 46 landStartTime, landDuration, waterStartTime, waterDuration 47 ) 48 water_then_land = calculate_finish_time( 49 waterStartTime, waterDuration, landStartTime, landDuration 50 ) 51 52 # Return the minimum finish time between both orderings 53 return min(land_then_water, water_then_land) 54

1class Solution { 2 /** 3 * Calculates the earliest finish time for completing tasks from two different categories. 4 * Tasks can be completed in either order: land tasks first then water tasks, or vice versa. 5 * 6 * @param landStartTime array of start times for land tasks 7 * @param landDuration array of durations for land tasks 8 * @param waterStartTime array of start times for water tasks 9 * @param waterDuration array of durations for water tasks 10 * @return the minimum time to complete all tasks 11 */ 12 public int earliestFinishTime( 13 int[] landStartTime, int[] landDuration, int[] waterStartTime, int[] waterDuration) { 14 15 // Calculate finish time if land tasks are done first, then water tasks 16 int landThenWater = calculateFinishTime(landStartTime, landDuration, waterStartTime, waterDuration); 17 18 // Calculate finish time if water tasks are done first, then land tasks 19 int waterThenLand = calculateFinishTime(waterStartTime, waterDuration, landStartTime, landDuration); 20 21 // Return the minimum of both approaches 22 return Math.min(landThenWater, waterThenLand); 23 } 24 25 /** 26 * Helper method to calculate the finish time when completing first category tasks 27 * followed by second category tasks. 28 * 29 * @param firstStartTimes array of start times for first category tasks 30 * @param firstDurations array of durations for first category tasks 31 * @param secondStartTimes array of start times for second category tasks 32 * @param secondDurations array of durations for second category tasks 33 * @return the total time to complete all tasks in the specified order 34 */ 35 private int calculateFinishTime(int[] firstStartTimes, int[] firstDurations, 36 int[] secondStartTimes, int[] secondDurations) { 37 38 // Find the earliest possible completion time for all first category tasks 39 int earliestFirstCategoryEnd = Integer.MAX_VALUE; 40 for (int i = 0; i < firstStartTimes.length; i++) { 41 int taskEndTime = firstStartTimes[i] + firstDurations[i]; 42 earliestFirstCategoryEnd = Math.min(earliestFirstCategoryEnd, taskEndTime); 43 } 44 45 // Find the minimum total completion time considering all second category tasks 46 int minimumTotalTime = Integer.MAX_VALUE; 47 for (int i = 0; i < secondStartTimes.length; i++) { 48 // Second task can only start after both: first category ends and its own start time 49 int secondTaskStart = Math.max(earliestFirstCategoryEnd, secondStartTimes[i]); 50 int totalTime = secondTaskStart + secondDurations[i]; 51 minimumTotalTime = Math.min(minimumTotalTime, totalTime); 52 } 53 54 return minimumTotalTime; 55 } 56} 57

1class Solution { 2public: 3 int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration, 4 vector<int>& waterStartTime, vector<int>& waterDuration) { 5 // Calculate the minimum time when starting with land activities first, then water 6 int landFirstTime = calculateMinimumTime(landStartTime, landDuration, 7 waterStartTime, waterDuration); 8 9 // Calculate the minimum time when starting with water activities first, then land 10 int waterFirstTime = calculateMinimumTime(waterStartTime, waterDuration, 11 landStartTime, landDuration); 12 13 // Return the minimum of both approaches 14 return min(landFirstTime, waterFirstTime); 15 } 16 17private: 18 int calculateMinimumTime(vector<int>& firstStartTimes, vector<int>& firstDurations, 19 vector<int>& secondStartTimes, vector<int>& secondDurations) { 20 // Find the earliest completion time among all first activities 21 int earliestFirstCompletion = INT_MAX; 22 for (int i = 0; i < firstStartTimes.size(); ++i) { 23 int completionTime = firstStartTimes[i] + firstDurations[i]; 24 earliestFirstCompletion = min(earliestFirstCompletion, completionTime); 25 } 26 27 // Find the minimum total time by trying each second activity 28 int minimumTotalTime = INT_MAX; 29 for (int i = 0; i < secondStartTimes.size(); ++i) { 30 // Second activity can only start after both: 31 // 1. First activity is completed (earliestFirstCompletion) 32 // 2. Second activity's start time is reached (secondStartTimes[i]) 33 int secondActivityStart = max(earliestFirstCompletion, secondStartTimes[i]); 34 int totalTime = secondActivityStart + secondDurations[i]; 35 minimumTotalTime = min(minimumTotalTime, totalTime); 36 } 37 38 return minimumTotalTime; 39 } 40}; 41

1/** 2 * Calculates the earliest finish time by considering both possible orders: 3 * land tasks first then water tasks, or water tasks first then land tasks. 4 * 5 * @param landStartTime - Array of start times for land tasks 6 * @param landDuration - Array of durations for land tasks 7 * @param waterStartTime - Array of start times for water tasks 8 * @param waterDuration - Array of durations for water tasks 9 * @returns The minimum finish time across both possible orderings 10 */ 11function earliestFinishTime( 12 landStartTime: number[], 13 landDuration: number[], 14 waterStartTime: number[], 15 waterDuration: number[], 16): number { 17 // Calculate finish time when doing land tasks first, then water tasks 18 const landFirstFinishTime = calc(landStartTime, landDuration, waterStartTime, waterDuration); 19 20 // Calculate finish time when doing water tasks first, then land tasks 21 const waterFirstFinishTime = calc(waterStartTime, waterDuration, landStartTime, landDuration); 22 23 // Return the minimum of both possible orderings 24 return Math.min(landFirstFinishTime, waterFirstFinishTime); 25} 26 27/** 28 * Calculates the minimum finish time when completing first set of tasks 29 * before starting the second set of tasks. 30 * 31 * @param firstStartTimes - Start times for the first set of tasks 32 * @param firstDurations - Durations for the first set of tasks 33 * @param secondStartTimes - Start times for the second set of tasks 34 * @param secondDurations - Durations for the second set of tasks 35 * @returns The minimum finish time for this ordering 36 */ 37function calc( 38 firstStartTimes: number[], 39 firstDurations: number[], 40 secondStartTimes: number[], 41 secondDurations: number[] 42): number { 43 // Find the earliest completion time among all first tasks 44 let earliestFirstTaskCompletion = Number.MAX_SAFE_INTEGER; 45 for (let i = 0; i < firstStartTimes.length; i++) { 46 const taskEndTime = firstStartTimes[i] + firstDurations[i]; 47 earliestFirstTaskCompletion = Math.min(earliestFirstTaskCompletion, taskEndTime); 48 } 49 50 // Find the minimum total completion time considering all second tasks 51 let minimumTotalTime = Number.MAX_SAFE_INTEGER; 52 for (let i = 0; i < secondStartTimes.length; i++) { 53 // Second task can only start after both: first tasks complete AND its own start time 54 const actualSecondTaskStart = Math.max(earliestFirstTaskCompletion, secondStartTimes[i]); 55 const totalCompletionTime = actualSecondTaskStart + secondDurations[i]; 56 minimumTotalTime = Math.min(minimumTotalTime, totalCompletionTime); 57 } 58 59 return minimumTotalTime; 60} 61

Solution Approach

The solution implements the greedy enumeration strategy using a helper function calc that computes the earliest completion time for a given order of rides.

The calc function takes four parameters:

a1, t1: start times and durations for the first type of ride
a2, t2: start times and durations for the second type of ride

Inside calc, we first find the earliest possible end time for any ride of the first type:

min_end = min(a + t for a, t in zip(a1, t1))

This iterates through all rides of the first type and calculates startTime + duration for each, taking the minimum.

Next, we enumerate all possible choices for the second ride and find the one that finishes earliest:

return min(max(a, min_end) + t for a, t in zip(a2, t2))

For each second ride with start time a and duration t:

We can board it at time max(a, min_end) (either when it opens or right after finishing the first ride, whichever is later)
We finish at time max(a, min_end) + t
We return the minimum completion time across all second ride options

The main function calls calc twice to consider both possible orders:

x = calc(landStartTime, landDuration, waterStartTime, waterDuration) - land rides first, then water rides
y = calc(waterStartTime, waterDuration, landStartTime, landDuration) - water rides first, then land rides

Finally, we return min(x, y) to get the earliest possible completion time across both orders.

The time complexity is O(n + m) where n is the number of land rides and m is the number of water rides, as we iterate through each ride list a constant number of times. The space complexity is O(1) as we only use a few variables to track intermediate results.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

Land rides: landStartTime = [1, 4], landDuration = [3, 2]
Water rides: waterStartTime = [2, 5], waterDuration = [2, 1]

Step 1: Consider Land Rides First

First, find the earliest we can finish any land ride:

Land ride 0: starts at 1, duration 3 → finishes at 1 + 3 = 4
Land ride 1: starts at 4, duration 2 → finishes at 4 + 2 = 6
min_end = min(4, 6) = 4

Now, after finishing a land ride at time 4, determine when we can complete each water ride:

Water ride 0: opens at 2, duration 2
- Can board at max(4, 2) = 4 (ride already open)
- Finishes at 4 + 2 = 6
Water ride 1: opens at 5, duration 1
- Can board at max(4, 5) = 5 (must wait for it to open)
- Finishes at 5 + 1 = 6

Best completion time for land-then-water: min(6, 6) = 6

Step 2: Consider Water Rides First

Find the earliest we can finish any water ride:

Water ride 0: starts at 2, duration 2 → finishes at 2 + 2 = 4
Water ride 1: starts at 5, duration 1 → finishes at 5 + 1 = 6
min_end = min(4, 6) = 4

After finishing a water ride at time 4, determine when we can complete each land ride:

Land ride 0: opens at 1, duration 3
- Can board at max(4, 1) = 4 (ride already open)
- Finishes at 4 + 3 = 7
Land ride 1: opens at 4, duration 2
- Can board at max(4, 4) = 4 (ride just opened)
- Finishes at 4 + 2 = 6

Best completion time for water-then-land: min(7, 6) = 6

Step 3: Final Answer

Compare both orders: min(6, 6) = 6

The earliest possible time to finish both rides is 6. This can be achieved by either:

Taking land ride 0 (1→4), then water ride 0 (4→6), or
Taking water ride 0 (2→4), then land ride 1 (4→6)

Time and Space Complexity

Time Complexity: O(n + m), where n is the length of land ride arrays and m is the length of water ride arrays.

The calc function performs two main operations:

Computing min_end iterates through all elements in the first arrays using zip(a1, t1), which takes O(len(a1)) time
Finding the minimum among all possible end times iterates through all elements in the second arrays using zip(a2, t2), which takes O(len(a2)) time

The main function calls calc twice:

First call: O(n) for processing land rides + O(m) for processing water rides = O(n + m)
Second call: O(m) for processing water rides + O(n) for processing land rides = O(m + n)
Final min operation: O(1)

Total time complexity: O(n + m) + O(m + n) + O(1) = O(n + m)

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

Variables min_end, x, and y each store single integer values
The generator expressions in min() functions don't create intermediate lists but compute values on-the-fly
No additional data structures are created that scale with input size

Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Calculating Start Time for Second Ride

A common mistake is forgetting that the second ride might open after you finish the first ride. Many developers incorrectly assume they can always start the second ride immediately after finishing the first.

Incorrect approach:

# Wrong: Assumes second ride is always available when first finishes min_first_end = min(start + duration for start, duration in zip(first_starts, first_durations)) # Incorrectly just adds duration without checking if ride is open return min(min_first_end + duration for duration in second_durations)

Correct approach:

# Must take the maximum of when we finish first ride and when second ride opens return min(max(start, min_first_end) + duration  for start, duration in zip(second_starts, second_durations))

Pitfall 2: Only Considering One Order of Rides

Another frequent error is assuming one particular order (like always doing land rides first) will give the optimal solution, without checking both possibilities.

Incorrect approach:

def earliestFinishTime(self, landStartTime, landDuration, waterStartTime, waterDuration):  # Wrong: Only considers land rides first  min_land_end = min(s + d for s, d in zip(landStartTime, landDuration))  return min(max(s, min_land_end) + d for s, d in zip(waterStartTime, waterDuration))

Why this fails: Consider this example:

Land ride: starts at time 10, duration 1 (finishes at 11)
Water ride: starts at time 0, duration 2 (finishes at 2)

If we only try land-first-then-water: 10 + 1 = 11, then water at max(0, 11) + 2 = 13 But water-first-then-land gives: 0 + 2 = 2, then land at max(10, 2) + 1 = 11

The optimal answer is 11, not 13.

Pitfall 3: Misunderstanding the "Exactly One" Constraint

Some might try to optimize by selecting multiple rides or skipping categories entirely.

Incorrect interpretation:

# Wrong: Tries to find minimum across all rides regardless of category all_rides = [(s, d) for s, d in zip(landStartTime + waterStartTime,  landDuration + waterDuration)] # This doesn't ensure we take one from each category

Correct understanding: The problem requires exactly one ride from each category, not just any two rides or the two fastest rides overall.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = { 2 '2': 'abc', 3 '3': 'def', 4 '4': 'ghi', 5 '5': 'jkl', 6 '6': 'mno', 7 '7': 'pqrs', 8 '8': 'tuv', 9 '9': 'wxyz', 10} 11 12def letter_combinations_of_phone_number(digits): 13 def dfs(path, res): 14 if len(path) == len(digits): 15 res.append(''.join(path)) 16 return 17 18 next_number = digits[len(path)] 19 for letter in KEYBOARD[next_number]: 20 path.append(letter) 21 dfs(path, res) 22 path.pop() 23 24 res = [] 25 dfs([], res) 26 return res 27

1private static final Map<Character, char[]> KEYBOARD = Map.of( 2 '2', "abc".toCharArray(), 3 '3', "def".toCharArray(), 4 '4', "ghi".toCharArray(), 5 '5', "jkl".toCharArray(), 6 '6', "mno".toCharArray(), 7 '7', "pqrs".toCharArray(), 8 '8', "tuv".toCharArray(), 9 '9', "wxyz".toCharArray() 10); 11 12public static List<String> letterCombinationsOfPhoneNumber(String digits) { 13 List<String> res = new ArrayList<>(); 14 dfs(new StringBuilder(), res, digits.toCharArray()); 15 return res; 16} 17 18private static void dfs(StringBuilder path, List<String> res, char[] digits) { 19 if (path.length() == digits.length) { 20 res.add(path.toString()); 21 return; 22 } 23 char next_digit = digits[path.length()]; 24 for (char letter : KEYBOARD.get(next_digit)) { 25 path.append(letter); 26 dfs(path, res, digits); 27 path.deleteCharAt(path.length() - 1); 28 } 29} 30

1const KEYBOARD = { 2 '2': 'abc', 3 '3': 'def', 4 '4': 'ghi', 5 '5': 'jkl', 6 '6': 'mno', 7 '7': 'pqrs', 8 '8': 'tuv', 9 '9': 'wxyz', 10} 11 12function letter_combinations_of_phone_number(digits) { 13 let res = []; 14 dfs(digits, [], res); 15 return res; 16} 17 18function dfs(digits, path, res) { 19 if (path.length === digits.length) { 20 res.push(path.join('')); 21 return; 22 } 23 let next_number = digits.charAt(path.length); 24 for (let letter of KEYBOARD[next_number]) { 25 path.push(letter); 26 dfs(digits, path, res); 27 path.pop(); 28 } 29} 30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know