0506EasyArrayTwo PointersBinary SearchGreedySorting

Forge and Kiln Booking

Tracked in this browser only

Trains the technique from

LeetCode 3633Earliest Finish Time for Land and Water Rides I

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

An apprentice has to be signed off on exactly one forge session and exactly one kiln session before the day is over, and the two sessions may be taken in either order.

Forge session i unlocks at minute forgeOpen[i] and, once the apprentice begins it, occupies forgeLength[i] minutes without a break. Kiln session j unlocks at minute kilnOpen[j] and occupies kilnLength[j] minutes. A session may be begun at any minute at or after the minute it unlocks, and the apprentice may idle for as long as needed while waiting.

The apprentice is free from minute 0, cannot be in both workshops at the same time, and must finish one session before beginning the other. Return the earliest minute at which both chosen sessions can be finished.

Examples

Example 1

Input: forgeOpen = [8, 3], forgeLength = [5, 6], kilnOpen = [1, 7], kilnLength = [4, 2]
Output: 11

Forge session 1 unlocks at minute 3 and runs to minute 9. Kiln session 1 unlocks at minute 7, so it can begin at minute 9 and it runs to minute 11.

Example 2

Input: forgeOpen = [1], forgeLength = [1000], kilnOpen = [1000], kilnLength = [1]
Output: 1002

The kiln session unlocks at minute 1000 and takes a single minute, ending at minute 1001. The forge session has been unlocked since minute 1, so it begins at minute 1001 and runs 1000 minutes to minute 2001.

Example 3

Input: forgeOpen = [9, 1], forgeLength = [1, 30], kilnOpen = [4, 40], kilnLength = [1, 1]
Output: 10

Kiln session 0 unlocks at minute 4 and takes 1 minute, ending at minute 5. Forge session 0 unlocks at minute 9, so it waits until minute 9 and takes 1 minute, ending at minute 10.

Constraints

1 <= forgeOpen.length == forgeLength.length <= 100
1 <= kilnOpen.length == kilnLength.length <= 100
1 <= forgeOpen[i], forgeLength[i], kilnOpen[j], kilnLength[j] <= 1000

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def earliest_both_done(forgeOpen: list[int], forgeLength: list[int], kilnOpen: list[int], kilnLength: list[int]) -> int:

Java

public int earliestBothDone(int[] forgeOpen, int[] forgeLength, int[] kilnOpen, int[] kilnLength)

The intended approach

Time O(n + m): four linear scans over the two workshops.Space O(1): a handful of running minima.

Handle the two orders separately. Within one order, the second session ends at its own length added to the later of its unlock minute and the minute the first session ended, which never decreases when the first session ends later, so only the soonest possible end of the first session is worth trying. Compute that soonest end for one workshop, scan the other workshop for the cheapest follower, swap the two roles, and keep the smaller of the two results.

Pythonentry point: earliest_both_done

def earliest_both_done(forgeOpen, forgeLength, kilnOpen, kilnLength):
    # For a fixed order, the finish minute of the second session is a
    # non-decreasing function of the minute the first session ended, so only the
    # earliest possible end of the first session matters. Take that earliest end
    # for one workshop, then scan the other workshop for the best follower, and
    # repeat with the roles swapped.
    # O(n + m) time, O(1) space.
    def soonest_end(open_at, length):
        best = open_at[0] + length[0]
        for i in range(1, len(open_at)):
            end = open_at[i] + length[i]
            if end < best:
                best = end
        return best

    def follow(ready, open_at, length):
        best = None
        for i in range(len(open_at)):
            begin = ready if ready > open_at[i] else open_at[i]
            end = begin + length[i]
            if best is None or end < best:
                best = end
        return best

    first = follow(soonest_end(forgeOpen, forgeLength), kilnOpen, kilnLength)
    second = follow(soonest_end(kilnOpen, kilnLength), forgeOpen, forgeLength)
    return first if first < second else second

The obvious version

Try every forge session against every kiln session, and for each pair play out both orders explicitly, waiting where the second session has not unlocked yet. Report the smallest finishing minute seen. O(n * m).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_earliest_both_done(forgeOpen, forgeLength, kilnOpen, kilnLength):
    best = None
    for i in range(len(forgeOpen)):
        for j in range(len(kilnOpen)):
            a = forgeOpen[i] + forgeLength[i]
            a = max(a, kilnOpen[j]) + kilnLength[j]
            b = kilnOpen[j] + kilnLength[j]
            b = max(b, forgeOpen[i]) + forgeLength[i]
            for end in (a, b):
                if best is None or end < best:
                    best = end
    return best

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in