3633. Earliest Finish Time for Land and Water Rides I

Time: O(n + m)

Space: O(1)

Intuition

You must complete one land ride and one water ride, but the order is flexible. For each order, only the earliest possible completion of the first ride type matters, because any later first completion cannot improve the final answer. Then evaluate all second rides against that earliest finish and take the minimum overall.

Algorithm

1Compute answer for order A->B and B->A separately, then return the smaller one.
2For one order, scan all first-type rides and compute earliestFirst = min(start[i] + duration[i]).
3Scan all second-type rides and compute finish = max(earliestFirst, secondStart[j]) + secondDuration[j].
4Track the minimum finish over all second rides for that order.
5Return min(order1Result, order2Result).

Example Walkthrough

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

1.Land first: earliest land finish is min(2+3, 5+2) = 5.
2.Then water finishes at min(max(5,4)+4, max(5,7)+1) = min(9,8) = 8.
3.Water first: earliest water finish is min(4+4, 7+1) = 8.
4.Then land finishes at min(max(8,2)+3, max(8,5)+2) = min(11,10) = 10.

Output: 8

Common Pitfalls

•Do not force a single order; both land->water and water->land must be checked.
•The second ride start time is constrained by both availability and your previous completion time, so use max(...).
•Avoid O(n*m) pair enumeration; earliest first completion collapses each order to linear scans.

3633.cs

// Approach: Evaluate both valid orders (land then water, and water then land) and take the minimum finish time.
// For a fixed order, first find the earliest completion among the first ride type, then combine with each second ride using 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)
    {
        // Calculate finish time if land tasks are done first, then water tasks
        int landThenWaterTime = CalculateSequentialFinishTime(
            landStartTime, landDuration, waterStartTime, waterDuration);

        // Calculate finish time if water tasks are done first, then land tasks
        int waterThenLandTime = CalculateSequentialFinishTime(
            waterStartTime, waterDuration, landStartTime, landDuration);

        // Return the minimum of the two possible orderings
        return Math.Min(landThenWaterTime, waterThenLandTime);
    }

    private int CalculateSequentialFinishTime(
        int[] firstStartTimes, int[] firstDurations,
        int[] secondStartTimes, int[] secondDurations)
    {
        // Find the earliest completion time among all first tasks
        int earliestFirstTaskCompletion = int.MaxValue;
        for (int i = 0; i < firstStartTimes.Length; i++)
        {
            int taskEndTime = firstStartTimes[i] + firstDurations[i];
            earliestFirstTaskCompletion = Math.Min(earliestFirstTaskCompletion, taskEndTime);
        }

        // Find the earliest total completion time when starting second tasks
        // after completing at least one first task
        int earliestTotalCompletion = int.MaxValue;
        for (int i = 0; i < secondStartTimes.Length; i++)
        {
            // Second task can only start after both:
            // 1. Its own start time constraint
            // 2. At least one first task is complete
            int actualSecondTaskStart = Math.Max(earliestFirstTaskCompletion, secondStartTimes[i]);
            int totalCompletionTime = actualSecondTaskStart + secondDurations[i];
            earliestTotalCompletion = Math.Min(earliestTotalCompletion, totalCompletionTime);
        }

        return earliestTotalCompletion;
    }
}

Was this solution helpful?