3633. Earliest Finish Time for Land and Water Rides I

Easy

Leetcode Link

Problem Description

You are given two categories of theme park attractions: land rides and water rides.

Land rides:
- landStartTime[i] – the earliest time the ith land ride can be boarded.
- landDuration[i] – how long the ith land ride lasts.
Water rides:
- waterStartTime[j] – the earliest time the jth water ride can be boarded.
- waterDuration[j] – how long the jth water ride lasts.

A tourist must experience exactly one ride from each category, in either order.

A ride may be started at its opening time or any later moment.
If a ride is started at time t, it finishes at time t + duration.
Immediately after finishing one ride the tourist may board the other (if it is already open) or wait until it opens.

Return the earliest possible time at which the tourist can finish both rides.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

Since the tourist has to go on one land ride and one water ride, and can do them in any order, we can try both orders to find which one can be finished earlier.

For each possible order, we want to pick the land ride (or water ride) that can finish as soon as possible. This is simply the ride with the smallest startTime + duration. Once we know when the first ride can be finished, the tourist moves directly to the second category—either boards the next ride immediately if it's open, or waits until its start time. For each ride in the second category, the finish time would be max(when first ride ends, start time of this ride) + duration. We check all options for the second ride and pick the earliest possible finish time.

Finally, we compare both orders (land-then-water, water-then-land) and return the smallest finish time.

Solution Approach

We approach the solution by considering both possible orders: doing a land ride first, then a water ride, and vice versa. The solution uses simple iteration and keeps track of minimum values to find the earliest way to finish both rides.

For each possible order:

Find the earliest finish of the first category:
- For all rides in the first category, calculate the end time as startTime[i] + duration[i].
- Let minEnd be the smallest of these finish times. This is the earliest time the tourist could be done with a ride from the first category.
Try all possible rides in the second category:
- For each ride in the second category, the tourist can only start this ride at time max(minEnd, startTime[j]) (either as soon as the first ride is done or, if it's not open yet, as soon as it opens).
- The finish time for trying this ride second is max(minEnd, startTime[j]) + duration[j].
- Keep track of the smallest of these finish times.
Repeat with order reversed:
- Do the same process but starting with water rides first, then land rides.
Final answer:
- The answer is the minimum finish time from both possible orders.

In the implementation, the calc function takes one category as the first ride and the other as the second. It computes minEnd for the first, then checks every ride in the second to find the earliest possible finish, as described above.

The code structure is simple and efficient, using only basic loops and the min and max functions.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Suppose there are the following rides:

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

Let's find the earliest possible time the tourist can finish both rides.

1. Try doing a land ride first, then a water ride:

Compute finish times for land rides:
- Land ride 0: ready at 2 + 5 = 7
- Land ride 1: ready at 4 + 3 = 7
- The earliest land ride can finish at 7.
Now try all water rides after finishing a land ride at 7:
- Water ride 0: opens at 5. Can start at max(7, 5) = 7, finishes at 7 + 2 = 9
- Water ride 1: opens at 3. Can start at max(7, 3) = 7, finishes at 7 + 6 = 13
- The earliest finish is 9 (using water ride 0).

2. Try doing a water ride first, then a land ride:

Compute finish times for water rides:
- Water ride 0: opens at 5, duration 2 → finishes at 5 + 2 = 7
- Water ride 1: opens at 3, duration 6 → finishes at 3 + 6 = 9
- The earliest water ride can finish is 7.
Now try all land rides after finishing a water ride at 7:
- Land ride 0: opens at 2. Can start at max(7, 2) = 7, finishes at 7 + 5 = 12
- Land ride 1: opens at 4. Can start at max(7, 4) = 7, finishes at 7 + 3 = 10
- The earliest finish is 10 (using land ride 1).

3. Compare both orders:

Land first → water: finish at 9
Water first → land: finish at 10

Earliest possible finish is 9.

This means the optimal plan is:

Do either land ride (both finish at 7), then water ride 0 (start at 7, finish at 9).

Solution Implementation

1from typing import List
2
3class Solution:
4    def earliestFinishTime(
5        self,
6        landStartTime: List[int],
7        landDuration: List[int],
8        waterStartTime: List[int],
9        waterDuration: List[int],
10    ) -> int:
11        # Calculates the earliest possible finish time given two sets of tasks
12        def calc(start1, duration1, start2, duration2):
13            # Find the earliest completion time among the first set
14            min_finish_first = min(s + d for s, d in zip(start1, duration1))
15            # For each task in the second set, calculate the finish time,
16            # considering it starts no earlier than both its available start time and the min_finish_first
17            return min(max(s, min_finish_first) + d for s, d in zip(start2, duration2))
18
19        # Two strategies: do land tasks before water, or water before land
20        finish_land_first = calc(landStartTime, landDuration, waterStartTime, waterDuration)
21        finish_water_first = calc(waterStartTime, waterDuration, landStartTime, landDuration)
22        # Return the optimal (earliest) finish time
23        return min(finish_land_first, finish_water_first)
24

1class Solution {
2    // Calculates the earliest finish time by evaluating both land->water and water->land schedules
3    public int earliestFinishTime(
4        int[] landStartTime, int[] landDuration, int[] waterStartTime, int[] waterDuration) {
5
6        // Option 1: land first, then water
7        int finishTimeOption1 = calc(landStartTime, landDuration, waterStartTime, waterDuration);
8
9        // Option 2: water first, then land
10        int finishTimeOption2 = calc(waterStartTime, waterDuration, landStartTime, landDuration);
11
12        // Return the earlier of the two finish times
13        return Math.min(finishTimeOption1, finishTimeOption2);
14    }
15
16    /**
17     * Helper method to calculate the minimum finish time.
18     * @param firstStart Array of starting times for the first task type
19     * @param firstDuration Array of durations for the first task type
20     * @param secondStart Array of starting times for the second task type
21     * @param secondDuration Array of durations for the second task type
22     * @return The minimum time to finish both tasks in sequence
23     */
24    private int calc(int[] firstStart, int[] firstDuration, int[] secondStart, int[] secondDuration) {
25        // Find the earliest possible time to finish any first-type task
26        int earliestFirstEnd = Integer.MAX_VALUE;
27        for (int i = 0; i < firstStart.length; ++i) {
28            earliestFirstEnd = Math.min(earliestFirstEnd, firstStart[i] + firstDuration[i]);
29        }
30
31        // For each second-type task, calculate the total time if starting after the earliest first-end
32        int minTotalEnd = Integer.MAX_VALUE;
33        for (int i = 0; i < secondStart.length; ++i) {
34            int secondActualStart = Math.max(earliestFirstEnd, secondStart[i]);
35            int secondEnd = secondActualStart + secondDuration[i];
36            minTotalEnd = Math.min(minTotalEnd, secondEnd);
37        }
38
39        return minTotalEnd;
40    }
41}
42

1#include <vector>
2#include <climits>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8    // Returns the earliest possible finish time by considering both land-first and water-first approaches
9    int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration, vector<int>& waterStartTime, vector<int>& waterDuration) {
10        // Try both sequences: land first then water, and water first then land
11        int landFirst = calc(landStartTime, landDuration, waterStartTime, waterDuration);
12        int waterFirst = calc(waterStartTime, waterDuration, landStartTime, landDuration);
13        // Return the earliest finish time from both approaches
14        return min(landFirst, waterFirst);
15    }
16
17    // Simulates first doing task set a1-t1, then a2-t2, and returns the earliest finish time for this sequence
18    int calc(vector<int>& a1, vector<int>& t1, vector<int>& a2, vector<int>& t2) {
19        int earliestEndFirst = INT_MAX;
20        // Find the minimum end time across all tasks in the first set
21        for (int i = 0; i < static_cast<int>(a1.size()); ++i) {
22            earliestEndFirst = min(earliestEndFirst, a1[i] + t1[i]);
23        }
24        int result = INT_MAX;
25        // For all tasks in the second set, find the earliest possible finish time
26        for (int i = 0; i < static_cast<int>(a2.size()); ++i) {
27            // Tasks in the second set cannot start before either their given start or finish of the first sequence
28            int startTime = max(earliestEndFirst, a2[i]);
29            result = min(result, startTime + t2[i]);
30        }
31        return result;
32    }
33};
34

1/**
2 * Calculates the earliest time to finish both land and water tasks,
3 * regardless of the order in which the task sets are done.
4 *
5 * @param landStartTime - Start times for the land tasks
6 * @param landDuration - Durations for the land tasks
7 * @param waterStartTime - Start times for the water tasks
8 * @param waterDuration - Durations for the water tasks
9 * @returns The earliest possible finish time
10 */
11function earliestFinishTime(
12    landStartTime: number[],
13    landDuration: number[],
14    waterStartTime: number[],
15    waterDuration: number[],
16): number {
17    // Calculate the earliest finish time starting with land first, then water
18    const finishLandFirst = calc(landStartTime, landDuration, waterStartTime, waterDuration);
19    // Calculate the earliest finish time starting with water first, then land
20    const finishWaterFirst = calc(waterStartTime, waterDuration, landStartTime, landDuration);
21    // Return the minimum of the two possible orders
22    return Math.min(finishLandFirst, finishWaterFirst);
23}
24
25/**
26 * Helper function to compute the earliest finish time by executing all tasks from
27 * the first group (a1/t1), then the second group (a2/t2), with proper waiting if needed.
28 *
29 * @param a1 - Start times for the first group of tasks
30 * @param t1 - Durations for the first group of tasks
31 * @param a2 - Start times for the second group of tasks
32 * @param t2 - Durations for the second group of tasks
33 * @returns The earliest possible finish time with this order
34 */
35function calc(
36    a1: number[],
37    t1: number[],
38    a2: number[],
39    t2: number[]
40): number {
41    // Find the earliest completion time of all first group tasks
42    let minEnd = Number.MAX_SAFE_INTEGER;
43    for (let i = 0; i < a1.length; i++) {
44        minEnd = Math.min(minEnd, a1[i] + t1[i]);
45    }
46
47    // For each task in the second group, compute when it can start (after all first group tasks are finished)
48    // and get the minimum possible end time for this group
49    let earliestTotalEnd = Number.MAX_SAFE_INTEGER;
50    for (let i = 0; i < a2.length; i++) {
51        // The task can only start after minEnd and its own start time
52        const start = Math.max(minEnd, a2[i]);
53        // Compute when this task will finish
54        const end = start + t2[i];
55        // Keep track of the earliest finish time among all options
56        earliestTotalEnd = Math.min(earliestTotalEnd, end);
57    }
58    return earliestTotalEnd;
59}
60

Time and Space Complexity

The time complexity of the code is O(n), where n is the number of rides in each theme park section (either land or water). This is because each zip operation in the calc function iterates over the entire input lists once, and each call to calc performs two linear scans. Since both input lists are of the same length, the overall time complexity remains O(n). The space complexity is O(1), as no extra space is used beyond a constant number of variables.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer techniques do you use to check if a string is a palindrome?

Fast-slow pointers

Two pointers moving in opposite direction

Sliding window

Prefix sum

I don't know