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

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.