Skip to main content
Talentd

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

EasyArrayTwo PointersBinary SearchGreedy10 min readAsked at: Amazon, Meta, Google +1
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 <= 100
  • landStartTime.length == landDuration.length == n
  • waterStartTime.length == waterDuration.length == m
  • 1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 1000

Approach Overview

Problem Overview: You must take exactly one land ride and one water ride. Each ride has an available start time and a duration. After finishing the land ride, you choose a water ride and may need to wait until it becomes available. The goal is to minimize the final completion time.

Approach 1: Brute Force Enumeration (O(n * m) time, O(1) space)

Try every possible pair of land and water rides. For each land ride i, compute when you finish it: finishLand = landStart[i] + landDuration[i]. Then iterate through every water ride j and compute the actual start time startWater = max(finishLand, waterStart[j]). The total completion time becomes startWater + waterDuration[j]. Track the minimum across all pairs. This approach is straightforward and demonstrates the core scheduling logic, but it becomes slow when both ride lists are large.

Approach 2: Enumeration + Greedy with Sorting and Binary Search (O((n + m) log m) time, O(m) space)

Instead of scanning every water ride for each land ride, sort water rides by their start time. For each land ride, compute finishLand and use binary search to find the first water ride whose start time is greater than or equal to this value. That ride lets you start immediately without extra waiting. For water rides that start earlier than finishLand, you can still take them but must wait until the land ride finishes. Precomputing the best candidate (such as minimum duration or minimum finish time) in suffix arrays lets you quickly determine the optimal choice after the binary search. This reduces the repeated scanning and turns the nested loop into a logarithmic lookup.

This method combines simple enumeration of land rides with a greedy choice among water rides. Sorting enables fast lookups, while binary search identifies the earliest feasible candidate. The technique is common in scheduling problems where one event must follow another.

Related concepts appear frequently in problems involving arrays, binary search, and greedy scheduling with sorted events. Two-pointer variants can further optimize scanning when both lists are processed in order.

Recommended for interviews: The enumeration + greedy approach with sorting and binary search is the expected solution. Interviewers often accept brute force as a starting point, but optimizing it with sorted events and fast lookups demonstrates strong problem‑solving and algorithmic thinking.

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 EnumerationO(n * m)O(1)Small inputs or when first reasoning about the scheduling logic
Enumeration + Greedy with Sorting & Binary SearchO((n + m) log m)O(m)Preferred approach for interviews and large datasets
Two Pointers on Sorted RidesO(n + m)O(1)When both ride lists are processed in sorted order and you scan them simultaneously

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 I easy or hard?
The problem is classified as Easy. The core idea is straightforward enumeration with scheduling logic, but recognizing the sorting and binary search optimization helps reduce time complexity and demonstrates stronger algorithmic understanding.
Earliest Finish Time for Land and Water Rides I Python/Java solution
Typical implementations enumerate land rides and use binary search over a sorted list of water rides. The logic is identical across Python, Java, C++, Go, and TypeScript: compute the land finish time, locate the best water ride, and update the global minimum completion time.
What is the best approach for Earliest Finish Time for Land and Water Rides I?
The most practical approach is enumeration combined with a greedy selection of water rides after sorting them by start time. For each land ride, compute the finish time and use binary search to locate the earliest compatible water ride. This reduces repeated scanning and achieves about O((n + m) log m) time complexity.
How to solve Earliest Finish Time for Land and Water Rides I in O((n+m) log m)?
Sort the water rides by their start time. For each land ride, compute when it finishes and use binary search to find the first water ride whose start time is at least that finish time. Combine that candidate with precomputed best options to determine the minimum completion time efficiently.
Is Earliest Finish Time for Land and Water Rides I asked at Google/Amazon/Meta?
Problems involving ride scheduling and earliest completion time commonly appear in interviews at companies like Amazon and Google under greedy or interval scheduling categories. Variations test your ability to combine sorting, binary search, and greedy decisions.
What data structure is used in Earliest Finish Time for Land and Water Rides I?
The solution primarily uses arrays along with sorting and binary search. Some implementations maintain auxiliary arrays such as suffix minimums to quickly determine the best water ride candidate after a binary search lookup.
What is the time complexity of Earliest Finish Time for Land and Water Rides I?
The brute force solution runs in O(n * m) because every land ride is paired with every water ride. The optimized method sorts water rides and performs binary search for each land ride, resulting in O((n + m) log m) time with O(m) extra space.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays