Problem Description

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

For each type of ride, you are given information about when they 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 ride 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 to do a land ride first that opens at time 2 with duration 3, you'll finish at time 5. Then if you want to do 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 ride exactly one attraction from each category, we have two possible orders: land ride first then water ride, or water ride first then land ride. We need to consider both orders and pick the one that finishes earliest.

For any given order, the key insight is that we want to minimize our total completion time. If we go with land rides first, we should pick the land ride that finishes earliest (minimizing waiting time for the water ride). This earliest finish time for the first ride becomes minEnd = min(startTime + duration) across all rides of that type.

Once we finish the first ride at time minEnd, we need to pick a water ride. For each possible water ride, we can board it at time max(minEnd, waterStartTime) - either right after finishing the land ride if the water ride is already open, or we wait until it opens. The total completion time would be max(minEnd, waterStartTime) + waterDuration.

To find the optimal solution for this order, we need to check all possible water rides and pick the one that gives us the earliest completion time: min(max(minEnd, waterStartTime[j]) + waterDuration[j]) for all j.

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

The final answer is the minimum completion time between these two orders. This greedy approach works because once we commit to an order, choosing the earliest-finishing first ride gives the second ride the best chance to start early, and then we simply pick whichever second ride can finish earliest given that constraint.

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

Solution Approach

The solution implements the greedy enumeration strategy using a helper function calc that computes the earliest completion time for a given order of rides.

The calc function takes four parameters:

• a1, t1: start times and durations for the first type of ride
• a2, t2: start times and durations for the second type of ride

Inside calc, we first find the earliest possible end time for any ride of the first type:

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

This iterates through all rides of the first type and calculates startTime + duration for each, taking the minimum.

Next, we enumerate all possible choices for the second ride and find the one that finishes earliest:

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

For each second ride with start time a and duration t:

• We can board it at time max(a, min_end) (either when it opens or right after finishing the first ride, whichever is later)
• We finish at time max(a, min_end) + t
• We return the minimum completion time across all second ride options

The main function calls calc twice to consider both possible orders:

1. x = calc(landStartTime, landDuration, waterStartTime, waterDuration) - land rides first, then water rides
2. y = calc(waterStartTime, waterDuration, landStartTime, landDuration) - water rides first, then land rides

Finally, we return min(x, y) to get the earliest possible completion time across both orders.

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

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

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

Step 1: Consider Land Rides First

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 4, duration 2 → finishes at 4 + 2 = 6
• min_end = min(4, 6) = 4

Now, after finishing a land ride at time 4, determine when we can complete each water ride:

• Water ride 0: opens at 2, duration 2
  • Can board at max(4, 2) = 4 (ride already open)
  • Finishes at 4 + 2 = 6
• Water ride 1: opens at 5, duration 1
  • Can board at max(4, 5) = 5 (must wait for it to open)
  • Finishes at 5 + 1 = 6

Best completion time for land-then-water: min(6, 6) = 6

Step 2: Consider Water Rides First

Find the earliest we can finish any water ride:

• Water ride 0: starts at 2, duration 2 → finishes at 2 + 2 = 4
• Water ride 1: starts at 5, duration 1 → finishes at 5 + 1 = 6
• min_end = min(4, 6) = 4

After finishing a water ride at time 4, determine when we can complete each land ride:

• Land ride 0: opens at 1, duration 3
  • Can board at max(4, 1) = 4 (ride already open)
  • Finishes at 4 + 3 = 7
• Land ride 1: opens at 4, duration 2
  • Can board at max(4, 4) = 4 (ride just opened)
  • Finishes at 4 + 2 = 6

Best completion time for water-then-land: min(7, 6) = 6

Step 3: Final Answer

Compare both orders: min(6, 6) = 6

The earliest possible time to finish both rides is 6. This can be achieved by either:

• Taking land ride 0 (1→4), then water ride 0 (4→6), or
• Taking water ride 0 (2→4), then land ride 1 (4→6)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m), where n is the length of land ride arrays and m is the length of water ride arrays.

The calc function performs two main operations:

• Computing min_end iterates through all elements in the first arrays using zip(a1, t1), which takes O(len(a1)) time
• Finding the minimum among all possible end times iterates through all elements in the second arrays using zip(a2, t2), which takes O(len(a2)) time

The main function calls calc twice:

• First call: O(n) for processing land rides + O(m) for processing water rides = O(n + m)
• Second call: O(m) for processing water rides + O(n) for processing land rides = O(m + n)
• Final min operation: O(1)

Total time complexity: O(n + m) + O(m + n) + O(1) = O(n + m)

Space Complexity: O(1)

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

Therefore, the space complexity is O(1).

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

Common Pitfalls

Pitfall 1: Incorrectly Calculating Start Time for Second Ride

A common mistake is forgetting that the second ride might open after you finish the first ride. Many developers incorrectly assume they can always start the second ride immediately after finishing the first.

Incorrect approach:

# Wrong: Assumes second ride is always available when first finishes
min_first_end = min(start + duration for start, duration in zip(first_starts, first_durations))
# Incorrectly just adds duration without checking if ride is open
return min(min_first_end + duration for duration in second_durations)

Correct approach:

# Must take the maximum of when we finish first ride and when second ride opens
return min(max(start, min_first_end) + duration 
          for start, duration in zip(second_starts, second_durations))

Pitfall 2: Only Considering One Order of Rides

Another frequent error is assuming one particular order (like always doing land rides first) will give the optimal solution, without checking both possibilities.

Incorrect approach:

def earliestFinishTime(self, landStartTime, landDuration, waterStartTime, waterDuration):
    # Wrong: Only considers land rides first
    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 this fails: Consider this example:

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

If we only try land-first-then-water: 10 + 1 = 11, then water at max(0, 11) + 2 = 13 But water-first-then-land gives: 0 + 2 = 2, then land at max(10, 2) + 1 = 11

The optimal answer is 11, not 13.

Pitfall 3: Misunderstanding the "Exactly One" Constraint

Some might try to optimize by selecting multiple rides or skipping categories entirely.

Incorrect interpretation:

# Wrong: Tries to find minimum across all rides regardless of category
all_rides = [(s, d) for s, d in zip(landStartTime + waterStartTime, 
                                     landDuration + waterDuration)]
# This doesn't ensure we take one from each category

Correct understanding: The problem requires exactly one ride from each category, not just any two rides or the two fastest rides overall.