Earliest Finish Time for Land and Water Rides I

easy array greedy enumeration

Problem

There are land rides and water rides. Land ride i opens at landStartTime[i] and lasts landDuration[i]; water ride j opens at waterStartTime[j] and lasts waterDuration[j]. A tourist must take exactly one ride from each category, in either order. A ride started at time t finishes at t + duration; the second ride begins as soon as it is open or right after the first ends, whichever is later. Return the earliest possible time to finish both rides.

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

Output9

Land ride 0: start at 2, finish at 6. Water ride 0 is open at 6, so start at 6 and finish at 9. No plan finishes earlier.

landStartTime (comma-separated)

landDuration (comma-separated)

waterStartTime (comma-separated)

waterDuration (comma-separated)

def earliestFinishTime(landStartTime, landDuration, waterStartTime, waterDuration):
    best = float("inf")
    # Try every (land ride, water ride) pair.
    for i in range(len(landStartTime)):
        for j in range(len(waterStartTime)):
            # Plan 1: land first, then water.
            land_done = landStartTime[i] + landDuration[i]
            plan1 = max(land_done, waterStartTime[j]) + waterDuration[j]
            # Plan 2: water first, then land.
            water_done = waterStartTime[j] + waterDuration[j]
            plan2 = max(water_done, landStartTime[i]) + landDuration[i]
            # Keep the better ordering for this pair.
            best = min(best, plan1, plan2)
    return best

function earliestFinishTime(landStartTime, landDuration, waterStartTime, waterDuration) {
  let best = Infinity;
  // Try every (land ride, water ride) pair.
  for (let i = 0; i < landStartTime.length; i++) {
    for (let j = 0; j < waterStartTime.length; j++) {
      // Plan 1: land first, then water.
      const landDone = landStartTime[i] + landDuration[i];
      const plan1 = Math.max(landDone, waterStartTime[j]) + waterDuration[j];
      // Plan 2: water first, then land.
      const waterDone = waterStartTime[j] + waterDuration[j];
      const plan2 = Math.max(waterDone, landStartTime[i]) + landDuration[i];
      // Keep the better ordering for this pair.
      best = Math.min(best, plan1, plan2);
    }
  }
  return best;
}

int earliestFinishTime(int[] landStartTime, int[] landDuration, int[] waterStartTime, int[] waterDuration) {
    int best = Integer.MAX_VALUE;
    // Try every (land ride, water ride) pair.
    for (int i = 0; i < landStartTime.length; i++) {
        for (int j = 0; j < waterStartTime.length; j++) {
            // Plan 1: land first, then water.
            int landDone = landStartTime[i] + landDuration[i];
            int plan1 = Math.max(landDone, waterStartTime[j]) + waterDuration[j];
            // Plan 2: water first, then land.
            int waterDone = waterStartTime[j] + waterDuration[j];
            int plan2 = Math.max(waterDone, landStartTime[i]) + landDuration[i];
            // Keep the better ordering for this pair.
            best = Math.min(best, Math.min(plan1, plan2));
        }
    }
    return best;
}

int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration, vector<int>& waterStartTime, vector<int>& waterDuration) {
    int best = INT_MAX;
    // Try every (land ride, water ride) pair.
    for (int i = 0; i < (int)landStartTime.size(); i++) {
        for (int j = 0; j < (int)waterStartTime.size(); j++) {
            // Plan 1: land first, then water.
            int landDone = landStartTime[i] + landDuration[i];
            int plan1 = max(landDone, waterStartTime[j]) + waterDuration[j];
            // Plan 2: water first, then land.
            int waterDone = waterStartTime[j] + waterDuration[j];
            int plan2 = max(waterDone, landStartTime[i]) + landDuration[i];
            // Keep the better ordering for this pair.
            best = min(best, min(plan1, plan2));
        }
    }
    return best;
}

Explanation

The tourist takes exactly one land ride and one water ride. Because the constraints are tiny (n, m ≤ 100), we can simply brute force every pairing of a land ride with a water ride — at most 10,000 pairs — and for each pair try both orderings.

For a fixed land ride i and water ride j there are two ways to schedule them. Land first: the land ride ends at landStartTime[i] + landDuration[i]; the water ride cannot begin before it is open, so it starts at max(landDone, waterStartTime[j]) and ends waterDuration[j] later.

Water first: symmetrically, the water ride ends at waterStartTime[j] + waterDuration[j] and the land ride then begins at max(waterDone, landStartTime[i]), ending landDuration[i] later. The max captures the rule that you may wait for a ride to open before boarding.

For each pair we keep the cheaper of the two orderings, and across all pairs we keep the global minimum in best. That final minimum is the earliest time both rides can be finished.

Example: with land rides opening at [2, 8] (durations [4, 1]) and one water ride opening at 6 (duration 3), the pair (land 0, water 0) done land-first finishes at max(2+4, 6) + 3 = 9, which is the earliest of all four plans.

Time: O(n · m) Space: O(1)