3635. Earliest Finish Time for Land and Water Rides II

Time: O(n + m)

Space: O(1)

Intuition

Even with larger constraints, the core observation is unchanged: for a chosen order of ride types, only the earliest possible finish of the first ride matters. Any slower first ride can only delay or equal the second ride start, never improve it. So each order reduces to two linear scans, and the final answer is the minimum over both orders.

Algorithm

1Define a helper for order A->B.
2In that helper, compute earliestA = min(aStart[i] + aDuration[i]) over all A rides.
3For each B ride, compute candidate = max(earliestA, bStart[j]) + bDuration[j].
4Take the minimum candidate for that order.
5Run helper twice: land->water and water->land, and return the smaller value.

Example Walkthrough

Input: landStartTime = [1, 8], landDuration = [5, 1], waterStartTime = [3, 10], waterDuration = [4, 2]

1.Land first: earliest land finish = min(1+5, 8+1) = 6.
2.Water completion candidates: max(6,3)+4 = 10, max(6,10)+2 = 12 -> order result 10.
3.Water first: earliest water finish = min(3+4, 10+2) = 7.
4.Land completion candidates: max(7,1)+5 = 12, max(7,8)+1 = 9 -> order result 9.

Output: 9

Common Pitfalls

•Do not attempt all pair combinations between both ride sets; that is unnecessary and too slow.
•When chaining rides, start time is constrained by both availability and previous completion, so max(...) is mandatory.
•Checking only one order can miss the optimal answer; always evaluate both directions.

3635.cs

// Approach: Evaluate both valid orders: land then water, and water then land.
// For a fixed order, find the earliest completion time of any first-type ride, then combine it with each second-type ride as max(firstCompletion, secondStart) + secondDuration.
// Time: O(n + m) Space: O(1)

public class Solution
{
    public int EarliestFinishTime(int[] landStartTime, int[] landDuration, int[] waterStartTime, int[] waterDuration)
    {
        int x = Calc(landStartTime, landDuration, waterStartTime, waterDuration);
        int y = Calc(waterStartTime, waterDuration, landStartTime, landDuration);
        return Math.Min(x, y);
    }

    private int Calc(int[] a1, int[] t1, int[] a2, int[] t2)
    {
        int minEnd = int.MaxValue;
        for (int i = 0; i < a1.Length; ++i)
        {
            minEnd = Math.Min(minEnd, a1[i] + t1[i]);
        }
        int ans = int.MaxValue;
        for (int i = 0; i < a2.Length; ++i)
        {
            ans = Math.Min(ans, Math.Max(minEnd, a2[i]) + t2[i]);
        }
        
        return ans;
    }
}

Was this solution helpful?