Show problems as
Classic problem #3635MediumArrayTwo PointersBinary SearchGreedySorting

Earliest Finish Time for Land and Water Rides II

Real-world version: Pair of Workshop Slots
Tracked in this browser only
Read Earliest Finish Time for Land and Water Rides II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A trainee at a maker space has to sit exactly one lathe session and exactly one welding session, and cannot be at both benches at the same time.

Lathe session i opens at minute latheOpen[i] and, once begun, keeps the trainee busy for latheRuns[i] minutes. Welding session j opens at minute weldOpen[j] and keeps the trainee busy for weldRuns[j] minutes. A session may begin at any minute at or after the minute it opens, never before, and the trainee is free to wait around for as long as needed between sessions.

The trainee books one session at each bench and sits them one after the other, in whichever order suits. Return the earliest minute by which both sessions can be finished.

Examples

Example 1

Input
latheOpen = [3, 20], latheRuns = [40, 5], weldOpen = [1], weldRuns = [6]
Output
25

Welding runs from minute 1 to minute 7, then the second lathe session opens at minute 20 and runs to minute 25, so both are done by minute 25.

Example 2

Input
latheOpen = [1], latheRuns = [10], weldOpen = [1], weldRuns = [10]
Output
21

There is one choice at each bench and they cannot overlap, so one runs from minute 1 to minute 11 and the other from minute 11 to minute 21.

Example 3

Input
latheOpen = [2, 9], latheRuns = [3, 1], weldOpen = [14, 4], weldRuns = [2, 7]
Output
12

The second lathe session runs from minute 9 to minute 10, and the welding session that opened at minute 14 runs to minute 16, so both finish by minute 16.

Constraints

  • 1 <= latheOpen.length == latheRuns.length <= 10^5
  • 1 <= weldOpen.length == weldRuns.length <= 10^5
  • 1 <= latheOpen[i], weldOpen[j] <= 10^8
  • 1 <= latheRuns[i], weldRuns[j] <= 10^8

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def earliest_both_done(latheOpen: list[int], latheRuns: list[int], weldOpen: list[int], weldRuns: list[int]) -> int:
Java
public int earliestBothDone(int[] latheOpen, int[] latheRuns, int[] weldOpen, int[] weldRuns)

More on the same topics