Problem Statement in English

You’re give two lists of rides, lst and wst, where lst[i] and wst[i] represent the start time of the i-th land and water ride respectively. You’re also given two lists of durations, ld and wd, where ld[i] and wd[i] represent the duration of the i-th land and water ride respectively.

You can only take one ride at a time. You can start a ride at its start time or any time after that.

Return the earliest time you can finish both a land and a water ride.

Approach

We either end up choosing a combination where we take a land ride first, or a water ride first. We can calculate the earliest finish time for both cases and return the minimum of the two.

So you need to arrive at the conclusion that the first ride you take will be the one that finishes earlier. Then all you need to do is pick the earliest finishing ride from the first list, and then calculate the earliest finishing time for the second ride based on that.

Just remember that when you’re working on the second ride you are only picking start times that are greater than or equal to the finish time of the first ride.

And we’re done!

Solution in Python


class Solution:
    def earliestFinishTime(self, lst: List[int], ld: List[int], wst: List[int], wd: List[int]) -> int:
        def helper(firstRideStart, firstRideDuration, secondRideStart, secondRideDuration):
            firstRideEnd = inf
            for i in range(len(firstRideStart)):
                firstRideEnd = min(firstRideEnd, firstRideStart[i] + firstRideDuration[i])
            
            res = inf
            for i in range(len(secondRideStart)):
                res = min(res, max(firstRideEnd, secondRideStart[i]) + secondRideDuration[i])

            return res

        return min(helper(lst, ld, wst, wd), helper(wst, wd, lst, ld))

Complexity

  • Time: $O(n + m)$
    Since we need to iterate through both lists of rides to calculate the earliest finish time, where n is the length of lst and m is the length of wst.

  • Space: $O(1)$
    Since we are using only a constant amount of extra space to store variables for calculations.

Mistakes I Made

I didn’t come to the realisation that the first ride will be the one that finishes earlier. I looked up the solution, and now I feel terrible :(

And we are done.