3633. Earliest Finish Time for Land and Water Rides I

Array
Brute Force
Simulation

TIME

List[int],

SPACE

O(1)

Intuition

For each selected land ride and water ride, there are only two possible orders:

land ride, then water ride
water ride, then land ride

Once the order is fixed, starting the first ride as early as possible is always optimal. The second ride starts either immediately after the first finishes or when it opens, whichever is later.

Approach

Initialize the answer to infinity.
For every land ride i and water ride j:
- calculate the finish time when taking land ride i first:
```
max(landStartTime[i] + landDuration[i], waterStartTime[j]) + waterDuration[j]
```
- calculate the finish time when taking water ride j first:
```
max(waterStartTime[j] + waterDuration[j], landStartTime[i]) + landDuration[i]
```
- update the answer with the smaller finish time
Return the answer.

Complexity

Time: O(n * m), check each land-water pair
Space: O(1)

Edge Cases

One ride opens after the other has already finished -> wait until it opens
Second ride is already open -> board immediately after the first ride
Multiple pairs give the same earliest finish time
One land ride and one water ride -> compare the two possible orders

Code

from typing import List


class Solution:
    def earliestFinishTime(
        self,
        landStartTime: List[int],
        landDuration: List[int],
        waterStartTime: List[int],
        waterDuration: List[int],
    ) -> int:
        """
        3633. Earliest Finish Time for Land and Water Rides I
        Time: O(n * m)
        Space: O(1)
        """
        answer = float("inf")

        for land_start, land_duration in zip(landStartTime, landDuration):
            for water_start, water_duration in zip(waterStartTime, waterDuration):
                land_first = max(land_start + land_duration, water_start) + water_duration
                water_first = max(water_start + water_duration, land_start) + land_duration
                answer = min(answer, land_first, water_first)

        return answer

/**
 * 3633. Earliest Finish Time for Land and Water Rides I
 * Time: O(n * m)
 * Space: O(1)
 */
class Solution {
    public int earliestFinishTime(
        int[] landStartTime,
        int[] landDuration,
        int[] waterStartTime,
        int[] waterDuration
    ) {
        int answer = Integer.MAX_VALUE;

        for (int land = 0; land < landStartTime.length; land++) {
            for (int water = 0; water < waterStartTime.length; water++) {
                int landFirst = Math.max(
                    landStartTime[land] + landDuration[land],
                    waterStartTime[water]
                ) + waterDuration[water];

                int waterFirst = Math.max(
                    waterStartTime[water] + waterDuration[water],
                    landStartTime[land]
                ) + landDuration[land];

                answer = Math.min(answer, Math.min(landFirst, waterFirst));
            }
        }

        return answer;
    }
}