Skip to main content
Talentd

Earliest Finish Time for Land and Water Rides II - Solution & Explanation

MediumArrayTwo PointersBinary SearchGreedy10 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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 * 104
  • landStartTime.length == landDuration.length == n
  • waterStartTime.length == waterDuration.length == m
  • 1 <= 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.

Solution

We can consider two orders of rides: first land rides then water rides, or first water rides then land rides.

For each order, we first calculate the earliest end time minEnd of the first type of ride, then enumerate the second type of ride and calculate the earliest end time of the second type of ride as max(minEnd, startTime) + duration, where startTime is the start time of the second type of ride. We take the minimum value among all possible earliest end times as the answer.

Finally, we return the minimum value between the answers of the two orders.

The time complexity is O(n + m), where n and m are the numbers of land rides and water rides respectively. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair EnumerationO(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 SortingO(n log n + m log m)O(1)When arrays are sorted and you want to avoid repeated binary searches

Video Solution

Earliest Finish Time for Land and Water Rides I and II | Story To Code | Leetcode 3633 & 3635 | MIK • codestorywithMIK • 8,928 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Earliest Finish Time for Land and Water Rides II easy or hard?
The problem is generally classified as Medium. The brute force solution is simple, but identifying the greedy pairing with sorting and binary search requires familiarity with scheduling patterns and efficient array searching.
Earliest Finish Time for Land and Water Rides II Python/Java solution
Most implementations iterate over land rides, compute their finish time, and use binary search on the sorted water rides to find the earliest compatible option. The same logic works across Python, Java, C++, Go, and TypeScript with O(n log n) complexity after sorting.
How to solve Earliest Finish Time for Land and Water Rides II in O(n)?
Pure O(n) is only achievable after the rides are already sorted. With sorted arrays, a two‑pointer scan can move through land and water rides once while maintaining the earliest valid water ride. This produces an O(n + m) traversal, though the full solution usually includes an initial O(n log n) sorting step.
What is the best approach for Earliest Finish Time for Land and Water Rides II?
The most practical approach uses greedy pairing with sorting and binary search. Sort the water rides by start time, compute the finish time for each land ride, and binary search the earliest water ride that can start after it. This reduces the search space dramatically and runs in O(n log n + m log m) time with O(1) extra space.
Is Earliest Finish Time for Land and Water Rides II asked at Google/Amazon/Meta?
Scheduling and pairing problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. They test understanding of greedy strategies, sorting, and binary search. Variants often involve pairing tasks, meetings, or rides while minimizing completion time.
What data structure is used in Earliest Finish Time for Land and Water Rides II?
The problem primarily relies on arrays combined with sorting and binary search. Some implementations also use two pointers to scan sorted arrays efficiently. No complex data structures are required beyond standard array operations.
What is the time complexity of Earliest Finish Time for Land and Water Rides II?
The optimized solution runs in O(n log n + m log m) time due to sorting the ride lists and performing binary search for each land ride. Space complexity remains O(1) if sorting is done in place. A naive brute force approach would take O(n * m) time by checking every pair.

Ready to solve this problem?

Practice Earliest Finish Time for Land and Water Rides II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays