Problem Description

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

For each category, you have information about when rides 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 choose to do 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 a land ride that opens at time 2 with duration 3, you'll finish at time 5. Then if you want to take 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.

Intuition

Since we need to take exactly one ride from each category, we have two possible orders: land ride first then water ride, or water ride first then land ride. We need to check both orders and find which one gives us the earliest completion time.

For any given order, the key insight is that we want to minimize the total time. When we finish the first ride, we want to start the second ride as soon as possible. But there's a constraint - we can't start the second ride before it opens.

Let's think about the optimal strategy for choosing rides in a fixed order (say land first, then water):

1. For the first category (land rides), we want to finish as early as possible. The earliest we can finish any land ride is min(landStartTime[i] + landDuration[i]) for all i. This gives us the minimum end time for the first ride.

2. For the second category (water rides), we need to consider two constraints:

   • We can't start before the water ride opens: waterStartTime[j]
   • We can't start before we finish the land ride: minEnd from step 1

   So we start the water ride at max(waterStartTime[j], minEnd) and finish at max(waterStartTime[j], minEnd) + waterDuration[j].

3. To get the overall minimum completion time, we try all possible water rides and pick the one that finishes earliest.

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

The solution elegantly captures this with the calc function that takes the start times and durations of rides in order. It first finds the minimum end time for the first category, then finds the minimum total completion time considering all options for the second category. By calling this function twice with the parameters swapped, we check both possible orders and return the minimum.

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

Solution Approach

The solution implements an enumeration and greedy approach by considering both possible orders of rides and selecting the minimum completion time.

The core of the solution is the helper function calc(a1, t1, a2, t2) which calculates the minimum completion time when taking rides in a specific order:

• a1, t1 represent the start times and durations of the first category
• a2, t2 represent the start times and durations of the second category

Step 1: Find the earliest end time for the first category

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

This calculates the minimum possible end time among all rides in the first category. For each ride i, the end time is startTime[i] + duration[i]. We take the minimum of all these values.

Step 2: Calculate the minimum total completion time

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

For each ride in the second category:

• We can start at time max(a, min_end) where:
  • a is the ride's opening time
  • min_end is when we finish the first ride
  • We take the maximum because we must wait for both conditions to be satisfied
• The completion time is max(a, min_end) + t where t is the ride's duration
• We return the minimum completion time among all second category rides

Step 3: Check both orders

x = calc(landStartTime, landDuration, waterStartTime, waterDuration)
y = calc(waterStartTime, waterDuration, landStartTime, landDuration)
return min(x, y)

• x represents doing land rides first, then water rides
• y represents doing water rides first, then land rides
• We return the minimum of the two options

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 list a constant number of times. The space complexity is O(1) as we only use a few variables to store intermediate results.

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Given:

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

Step 1: Calculate for Land → Water order

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 6, duration 2 → finishes at 6 + 2 = 8
• Minimum end time for land rides: min_end = 4

Now calculate total completion time for each water ride option:

• Water ride 0: opens at 2, but we finish land at 4, so start at max(2, 4) = 4, finish at 4 + 5 = 9
• Water ride 1: opens at 4, we finish land at 4, so start at max(4, 4) = 4, finish at 4 + 1 = 5

Minimum completion time for Land → Water: 5 (choosing land ride 0 then water ride 1)

Step 2: Calculate for Water → Land order

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

• Water ride 0: starts at 2, duration 5 → finishes at 2 + 5 = 7
• Water ride 1: starts at 4, duration 1 → finishes at 4 + 1 = 5
• Minimum end time for water rides: min_end = 5

Now calculate total completion time for each land ride option:

• Land ride 0: opens at 1, but we finish water at 5, so start at max(1, 5) = 5, finish at 5 + 3 = 8
• Land ride 1: opens at 6, we finish water at 5, so start at max(6, 5) = 6, finish at 6 + 2 = 8

Minimum completion time for Water → Land: 8 (choosing water ride 1 then either land ride)

Step 3: Compare both orders

• Land → Water: 5
• Water → Land: 8
• Final answer: min(5, 8) = 5

The optimal strategy is to take land ride 0 (1→4), then immediately take water ride 1 (4→5), finishing at time 5.

Solution Implementation

Time and Space Complexity

The time complexity is O(n + m), where n is the length of the land rides arrays (landStartTime and landDuration) and m is the length of the water rides arrays (waterStartTime and waterDuration).

Breaking down the time complexity:

• The calc function is called twice
• Inside each calc function call:
  • min(a + t for a, t in zip(a1, t1)) iterates through all elements in the first pair of arrays, taking O(len(a1)) time
  • min(max(a, min_end) + t for a, t in zip(a2, t2)) iterates through all elements in the second pair of arrays, taking O(len(a2)) time
• First call to calc: O(n) + O(m) = O(n + m)
• Second call to calc: O(m) + O(n) = O(m + n)
• Finding the minimum of x and y: O(1)
• Total: O(n + m) + O(m + n) = O(n + m)

The space complexity is O(1) as 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

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

Common Pitfalls

Pitfall 1: Incorrectly Calculating the Earliest Completion Time

A common mistake is to separately find the minimum start time and minimum duration for each category, then combine them. This approach fails because the ride with the earliest start time might not be the same ride with the shortest duration.

Incorrect approach:

# WRONG: Finding minimum start and duration separately
min_land_start = min(landStartTime)
min_land_duration = min(landDuration)
min_land_end = min_land_start + min_land_duration  # This is incorrect!

Why it fails: Consider land rides with:

• Ride A: starts at time 1, duration 10 (ends at time 11)
• Ride B: starts at time 5, duration 2 (ends at time 7)

The incorrect approach would calculate: min_start(1) + min_duration(2) = 3, but you cannot combine attributes from different rides. The actual minimum end time is 7 (from Ride B).

Correct approach:

# CORRECT: Calculate end time for each ride, then find minimum
min_land_end = min(start + duration 
                   for start, duration in zip(landStartTime, landDuration))

Pitfall 2: Forgetting to Consider Both Ride Orders

Another mistake is assuming one specific order (like always doing land rides first) without checking if the opposite order might yield a better result.

Incorrect approach:

# WRONG: Only considering one order
def earliestFinishTime(self, landStartTime, landDuration, waterStartTime, waterDuration):
    # Only calculates land → water order
    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 it fails: Consider:

• Land ride: starts at 10, duration 1 (ends at 11)
• Water ride: starts at 0, duration 2 (ends at 2)

If we do land first: finish at time 11, then water at time 11, total = 13 If we do water first: finish at time 2, then land at time 10, total = 11

The water-first order is clearly better.

Correct approach:

# CORRECT: Check both orders and return minimum
land_first = calculate_finish_time(landStartTime, landDuration, 
                                  waterStartTime, waterDuration)
water_first = calculate_finish_time(waterStartTime, waterDuration, 
                                   landStartTime, landDuration)
return min(land_first, water_first)

Pitfall 3: Misunderstanding the Waiting Logic

Some might incorrectly assume that if the second ride hasn't opened yet when the first ride finishes, the total time should include a "waiting penalty" or that waiting makes the solution invalid.

Incorrect thinking:

# WRONG: Adding unnecessary complexity for waiting
if second_start > first_end:
    waiting_time = second_start - first_end
    total_time = first_end + waiting_time + second_duration  # Overcomplicating

Correct understanding: The formula max(second_start, first_end) + second_duration automatically handles waiting. If we finish the first ride before the second opens, we simply wait until it opens. The max() function elegantly captures this logic without explicit waiting time calculations.