LeetCode 3633 - Earliest Finish Time for Land and Water Rides I

The problem asks us to determine the earliest possible time a tourist can finish exactly one land ride and one water ride at a theme park, where rides may be taken in either order.

leetcodeeasyarraytwo-pointersbinary-searchgreedysorting

LeetCode Problem 3633

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, Binary Search, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to determine the earliest possible time a tourist can finish exactly one land ride and one water ride at a theme park, where rides may be taken in either order. Each ride has a start time, representing when it becomes available, and a duration, representing how long it takes to complete. A ride can start at its opening time or any later time, which means the tourist may have to wait if they finish a ride before the next ride is available.

The inputs are four arrays: landStartTime and landDuration for the land rides, and waterStartTime and waterDuration for the water rides. The output is a single integer representing the earliest finish time after completing one ride from each category.

Key points to note:

  • The tourist may take the rides in any order, so we must consider both sequences: land→water and water→land.
  • If a ride has not opened when the tourist finishes the previous ride, they must wait until its start time.
  • The constraints are small (1 <= n, m <= 100), so a solution with a nested iteration over both ride lists is feasible.

Important edge cases include:

  1. Only one ride in either category, forcing the order.
  2. The second ride opens after the first finishes, requiring a wait.
  3. All rides in one category are later than all rides in the other category, testing the correct calculation of wait times.

Approaches

Brute Force

The brute-force approach iterates over every possible pair of land and water rides, considering both possible orders: land→water and water→land. For each pair, the finish time is computed as the sum of the first ride's duration plus the start time of the second ride (or the time we finish the first ride, whichever is later). This ensures that we respect ride start times and durations. The minimum of all calculated finish times is the answer.

While this approach is correct, it involves iterating over n * m ride pairs and evaluating two sequences per pair, giving O(n * m) time complexity. Given the constraints, this is acceptable, but it is still worth exploring a slightly optimized approach.

Optimal Approach

The key insight is that for each ride in one category, the earliest possible second ride is the one that opens the soonest after finishing the first ride. Sorting both ride lists by start time allows us to efficiently determine, for each first ride, which second ride yields the earliest finish using binary search or a simple linear scan.

Because the constraints are small (max 100 rides per category), a simple nested iteration over both sorted arrays without binary search is sufficient and keeps the solution readable. This gives the same O(n * m) time complexity but reduces unnecessary comparisons in practice because we process rides in start-time order.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(1) Check all ride pairs in both orders; simple but exhaustive
Optimal O(n * m) O(1) Sort rides (optional) and iterate efficiently; same complexity in worst-case but can be faster in practice

Algorithm Walkthrough

  1. Initialize a variable earliest_finish with infinity to track the minimum finish time found.
  2. Iterate over each land ride i and each water ride j.
  3. For each pair (i, j), compute two possible sequences:
  • Land → Water: Start the land ride at landStartTime[i]. Finish at landStartTime[i] + landDuration[i]. Start the water ride at max(finish_land, waterStartTime[j]) and finish at start_water + waterDuration[j].
  • Water → Land: Start the water ride at waterStartTime[j]. Finish at waterStartTime[j] + waterDuration[j]. Start the land ride at max(finish_water, landStartTime[i]) and finish at start_land + landDuration[i].
  1. Update earliest_finish if either sequence gives a smaller finish time.
  2. After iterating all pairs, return earliest_finish.

Why it works: The algorithm checks all feasible ride pairings and both possible orders. By considering the maximum of the previous finish time and the next ride's start time, it ensures that rides cannot start before their availability, guaranteeing the earliest finish is correctly identified.

Python Solution

from typing import List

class Solution:
    def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
        earliest_finish = float('inf')
        n = len(landStartTime)
        m = len(waterStartTime)
        
        for i in range(n):
            for j in range(m):
                # Land -> Water
                finish_land = landStartTime[i] + landDuration[i]
                start_water = max(finish_land, waterStartTime[j])
                finish_water = start_water + waterDuration[j]
                earliest_finish = min(earliest_finish, finish_water)
                
                # Water -> Land
                finish_water_first = waterStartTime[j] + waterDuration[j]
                start_land = max(finish_water_first, landStartTime[i])
                finish_land_second = start_land + landDuration[i]
                earliest_finish = min(earliest_finish, finish_land_second)
        
        return earliest_finish

The code iterates through every combination of land and water rides, computing both orderings. It uses max to handle waiting for a ride to open and maintains the minimum finish time across all combinations.

Go Solution

func earliestFinishTime(landStartTime []int, landDuration []int, waterStartTime []int, waterDuration []int) int {
    earliestFinish := 1 << 30 // large number as infinity
    n := len(landStartTime)
    m := len(waterStartTime)
    
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            // Land -> Water
            finishLand := landStartTime[i] + landDuration[i]
            startWater := finishLand
            if waterStartTime[j] > finishLand {
                startWater = waterStartTime[j]
            }
            finishWater := startWater + waterDuration[j]
            if finishWater < earliestFinish {
                earliestFinish = finishWater
            }
            
            // Water -> Land
            finishWaterFirst := waterStartTime[j] + waterDuration[j]
            startLand := finishWaterFirst
            if landStartTime[i] > finishWaterFirst {
                startLand = landStartTime[i]
            }
            finishLandSecond := startLand + landDuration[i]
            if finishLandSecond < earliestFinish {
                earliestFinish = finishLandSecond
            }
        }
    }
    
    return earliestFinish
}

In Go, we use 1 << 30 as an effectively infinite starting value. Conditional statements replace Python's max for clarity. The nested loops and update logic remain the same.

Worked Examples

Example 1

Input: landStartTime = [2,8], landDuration = [4,1], waterStartTime = [6], waterDuration = [3]

Land Ride Water Ride Sequence Finish Time
0 0 Land→Water 9
0 0 Water→Land 13
1 0 Land→Water 12
1 0 Water→Land 10

Earliest finish time = 9

Example 2

Input: landStartTime = [5], landDuration = [3], waterStartTime = [1], waterDuration = [10]

Land Ride Water Ride Sequence Finish Time
0 0 Land→Water 18
0 0 Water→Land 14

Earliest finish time = 14

Complexity Analysis

Measure Complexity Explanation
Time O(n * m) Nested loops over all land and water ride pairs; constant time per pair
Space O(1) Only a few integer variables used for tracking minimum finish time

The algorithm scales quadratically with the number of rides but remains efficient given the constraint of maximum 100 rides per category.

Test Cases

# Basic examples
assert Solution().earliestFinishTime([2,8], [4,1], [6], [3]) == 9  # Example 1
assert Solution().earliestFinishTime([5], [3], [1], [10]) == 14    # Example 2

# Single ride in each category
assert Solution().earliestFinishTime([1], [1], [1], [1]) == 2

# Second ride opens after first finishes
assert Solution().earliestFinishTime([1], [3], [10], [2]) == 12

# All land rides earlier than water rides
assert Solution().earliestFinishTime([1,2,3], [1,1,1], [10,11], [2,2]) == 12

# All water rides earlier than land rides
assert Solution().earliestFinishTime([10,11], [2