Earliest Finish Time for Land and Water Rides I

Difficulty: Easy | Acceptance: 62.10% | Paid: No Topics: Array, Two Pointers, Binary Search, Greedy, Sorting

You are given two 0-indexed integer arrays landRides and waterRides. You want to take exactly one land ride and one water ride. You must take the land ride before the water ride. Return the minimum possible finish time.

The finish time is the sum of the duration of the land ride and the duration of the water ride.

• Examples
• Constraints
• Brute Force
• Greedy (Linear Scan)
• Sorting

Examples

Example 1

Input:

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

Output:

9

Explanation: ​​​​​​​

Plan A (land ride 0 → water ride 0):

Start land ride 0 at time landStartTime[0] = 2. Finish at 2 + landDuration[0] = 6.

Water ride 0 opens at time waterStartTime[0] = 6. Start immediately at 6, finish at 6 + waterDuration[0] = 9.

Plan B (water ride 0 → land ride 1):

Start water ride 0 at time waterStartTime[0] = 6. Finish at 6 + waterDuration[0] = 9.

Land ride 1 opens at landStartTime[1] = 8. Start at time 9, finish at 9 + landDuration[1] = 10.

Plan C (land ride 1 → water ride 0):

Start land ride 1 at time landStartTime[1] = 8. Finish at 8 + landDuration[1] = 9.

Water ride 0 opened at waterStartTime[0] = 6. Start at time 9, finish at 9 + waterDuration[0] = 12.

Plan D (water ride 0 → land ride 0):

Start water ride 0 at time waterStartTime[0] = 6. Finish at 6 + waterDuration[0] = 9.

Land ride 0 opened at landStartTime[0] = 2. Start at time 9, finish at 9 + landDuration[0] = 13.

Plan A gives the earliest finish time of 9.

Example 2

Input:

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

Output:

14

Explanation: ​​​​​​​

Plan A (water ride 0 → land ride 0):

Start water ride 0 at time waterStartTime[0] = 1. Finish at 1 + waterDuration[0] = 11.

Land ride 0 opened at landStartTime[0] = 5. Start immediately at 11 and finish at 11 + landDuration[0] = 14.

Plan B (land ride 0 → water ride 0):

Start land ride 0 at time landStartTime[0] = 5. Finish at 5 + landDuration[0] = 8.

Water ride 0 opened at waterStartTime[0] = 1. Start immediately at 8 and finish at 8 + waterDuration[0] = 18.

Plan A provides the earliest finish time of 14.​​​​​​​

Constraints

- 1 <= n, m <= 100
- landStartTime.length == landDuration.length == n
- waterStartTime.length == waterDuration.length == m
- 1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 1000

Brute Force

Intuition Check every possible pair of land and water rides to find the minimum sum.

Steps

• Initialize minTime to a very large value.
• Iterate through each land ride.
• For each land ride, iterate through each water ride.
• Calculate the sum of the current pair.
• Update minTime if the current sum is smaller.
• Return minTime.

from typing import List

class Solution:
    def earliestFinishTime(self, landRides: List[int], waterRides: List[int]) -> int:
        min_time = float('inf')
        for l in landRides:
            for w in waterRides:
                total = l + w
                if total < min_time:
                    min_time = total
        return min_time

Complexity

• Time: O(n * m), where n is the length of landRides and m is the length of waterRides.
• Space: O(1)
• Notes: This approach will time out on large inputs.

Greedy (Linear Scan)

Intuition To minimize the sum of two numbers, we should pick the smallest number from the first array and the smallest number from the second array.

Steps

• Find the minimum value in landRides.
• Find the minimum value in waterRides.
• Return the sum of these two minimum values.

from typing import List

class Solution:
    def earliestFinishTime(self, landRides: List[int], waterRides: List[int]) -> int:
        min_land = min(landRides)
        min_water = min(waterRides)
        return min_land + min_water

Complexity

• Time: O(n + m)
• Space: O(1)
• Notes: This is the optimal approach for this problem.

Sorting

Intuition If we sort the arrays, the smallest elements will be at the beginning (index 0). We can simply sum the first elements of both sorted arrays.

Steps

• Sort landRides in ascending order.
• Sort waterRides in ascending order.
• Return landRides[0] + waterRides[0].

from typing import List

class Solution:
    def earliestFinishTime(self, landRides: List[int], waterRides: List[int]) -> int:
        landRides.sort()
        waterRides.sort()
        return landRides[0] + waterRides[0]

Complexity

• Time: O(n log n + m log m)
• Space: O(1) or O(n) depending on the sorting algorithm’s space complexity.
• Notes: Sorting is less efficient than a linear scan but is a valid approach.