3635. Earliest Finish Time for Land and Water Rides II

Array
Binary Search
Sorting
Prefix Minimum
Suffix Minimum

TIME

List[int],

SPACE

O(n + m)

Intuition

If the first ride finishes at time t, then the best second ride from another category has two cases:

rides already open at or before t: finish time is t + duration, so choose the minimum duration among those rides
rides opening after t: finish time is start + duration, so choose the minimum finish time among those rides

This means each category can be preprocessed into a structure that answers:

best finish time if this category is taken after time t

Then try every land ride as the first ride and query the best water ride after it, and every water ride as the first ride and query the best land ride after it.

Approach

For one ride category:

Pair each ride as (start, duration) and sort by start.
Build starts, the sorted start times.
Build prefixMinDuration, where prefixMinDuration[i] is the minimum duration among rides 0..i.
Build suffixMinFinish, where suffixMinFinish[i] is the minimum start + duration among rides i..end.

To answer a query time t:

Binary search the last ride with start <= t.
If such a ride exists, candidate finish is t + prefixMinDuration[index].
If there is a later ride, candidate finish is suffixMinFinish[index + 1].
Return the smaller candidate.

Finally:

Preprocess land rides and water rides separately.
For each land ride, compute its finish time and query the water structure.
For each water ride, compute its finish time and query the land structure.
Return the minimum result.

Complexity

Time: O((n + m) log(n + m)), sorting plus binary searches for all first rides
Space: O(n + m), preprocessed arrays for both categories

Edge Cases

All second-category rides are already open -> prefix minimum duration handles this
No second-category ride is open yet -> suffix minimum finish handles waiting
First ride finish exactly equals a second ride's start -> it counts as already open
Only one ride in either category -> query helper still works

Code

from bisect import bisect_right
from typing import List


class RideOptions:
    def __init__(self, start_times: List[int], durations: List[int]) -> None:
        rides = sorted(zip(start_times, durations))
        n = len(rides)

        self.starts = [start for start, _ in rides]
        self.prefix_min_duration = [0] * n
        self.suffix_min_finish = [0] * n

        best_duration = float("inf")
        for index, (_, duration) in enumerate(rides):
            best_duration = min(best_duration, duration)
            self.prefix_min_duration[index] = best_duration

        best_finish = float("inf")
        for index in range(n - 1, -1, -1):
            start, duration = rides[index]
            best_finish = min(best_finish, start + duration)
            self.suffix_min_finish[index] = best_finish

    def earliest_finish_after(self, time: int) -> int:
        index = bisect_right(self.starts, time) - 1
        answer = float("inf")

        if index >= 0:
            answer = min(answer, time + self.prefix_min_duration[index])

        if index + 1 < len(self.starts):
            answer = min(answer, self.suffix_min_finish[index + 1])

        return answer


class Solution:
    def earliestFinishTime(
        self,
        landStartTime: List[int],
        landDuration: List[int],
        waterStartTime: List[int],
        waterDuration: List[int],
    ) -> int:
        """
        3635. Earliest Finish Time for Land and Water Rides II
        Time: O((n + m) log(n + m))
        Space: O(n + m)
        """
        land_options = RideOptions(landStartTime, landDuration)
        water_options = RideOptions(waterStartTime, waterDuration)

        answer = float("inf")

        for start, duration in zip(landStartTime, landDuration):
            answer = min(answer, water_options.earliest_finish_after(start + duration))

        for start, duration in zip(waterStartTime, waterDuration):
            answer = min(answer, land_options.earliest_finish_after(start + duration))

        return answer

import java.util.Arrays;

/**
 * 3635. Earliest Finish Time for Land and Water Rides II
 * Time: O((n + m) log(n + m))
 * Space: O(n + m)
 */
class Solution {
    public int earliestFinishTime(
        int[] landStartTime,
        int[] landDuration,
        int[] waterStartTime,
        int[] waterDuration
    ) {
        RideOptions landOptions = new RideOptions(landStartTime, landDuration);
        RideOptions waterOptions = new RideOptions(waterStartTime, waterDuration);

        int answer = Integer.MAX_VALUE;

        for (int index = 0; index < landStartTime.length; index++) {
            int finishTime = landStartTime[index] + landDuration[index];
            answer = Math.min(answer, waterOptions.earliestFinishAfter(finishTime));
        }

        for (int index = 0; index < waterStartTime.length; index++) {
            int finishTime = waterStartTime[index] + waterDuration[index];
            answer = Math.min(answer, landOptions.earliestFinishAfter(finishTime));
        }

        return answer;
    }

    private static class RideOptions {
        private final int[] starts;
        private final int[] prefixMinDuration;
        private final int[] suffixMinFinish;

        RideOptions(int[] startTimes, int[] durations) {
            int n = startTimes.length;
            int[][] rides = new int[n][2];

            for (int index = 0; index < n; index++) {
                rides[index][0] = startTimes[index];
                rides[index][1] = durations[index];
            }

            Arrays.sort(rides, (a, b) -> a[0] - b[0]);

            starts = new int[n];
            prefixMinDuration = new int[n];
            suffixMinFinish = new int[n];

            int bestDuration = Integer.MAX_VALUE;
            for (int index = 0; index < n; index++) {
                starts[index] = rides[index][0];
                bestDuration = Math.min(bestDuration, rides[index][1]);
                prefixMinDuration[index] = bestDuration;
            }

            int bestFinish = Integer.MAX_VALUE;
            for (int index = n - 1; index >= 0; index--) {
                bestFinish = Math.min(bestFinish, rides[index][0] + rides[index][1]);
                suffixMinFinish[index] = bestFinish;
            }
        }

        int earliestFinishAfter(int time) {
            int index = upperBound(starts, time) - 1;
            int answer = Integer.MAX_VALUE;

            if (index >= 0) {
                answer = Math.min(answer, time + prefixMinDuration[index]);
            }

            if (index + 1 < starts.length) {
                answer = Math.min(answer, suffixMinFinish[index + 1]);
            }

            return answer;
        }

        private int upperBound(int[] values, int target) {
            int left = 0;
            int right = values.length;

            while (left < right) {
                int mid = left + (right - left) / 2;
                if (values[mid] <= target) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            return left;
        }
    }
}