Kiln slots

A pottery studio has a week of firings booked and no idea how many kilns to buy. Every firing must run at its booked time, so the question is not how many firings there are but how many of them are ever burning at once.

The problem

Each firing is booked as a start hour and an end hour, counted from the start of the week. A kiln holds one firing at a time, and unloading is instant: a kiln that finishes at hour 6 can be started again at hour 6, so a firing ending exactly when another begins needs no second kiln.

Nothing may be delayed or split. Find the fewest kilns the studio can own and still honour the whole week.

Input. firings — a list of [start, end] pairs of integers, hours from the start of the week, with start < end. The list may be empty and the firings arrive in no particular order.

Output. An integer: the fewest kilns that cover every firing.

Example.

firings = [[0, 6], [5, 9], [8, 12]]   ->  2

Between hours 5 and 6 the first two firings run together, and between 8 and 9 the last two do — but the first and the last never share an hour, so the same kiln can serve both. Two kilns are enough and one is not.

A second example, with more firings but no more kilns, followed by the same count of firings needing four:

firings = [[2, 5], [5, 8], [8, 11], [11, 14]]   ->  1
firings = [[0, 4], [1, 5], [2, 6], [3, 7]]      ->  4

The first is a relay: each firing starts exactly when the previous one ends. In the second, hour 3 to 4 lies inside all four firings at once.

Constraints.

• 0 <= len(firings) <= 10^5
• 0 <= start < end <= 10^4

Hints

Approach

Brute force

For every firing, count how many others cover its start hour and take the largest count: n² pair tests, ten billion for a hundred thousand firings. Walking the timeline hour by hour is O(n · H), no better once the week is measured in fine units.

The insight

The number of kilns needed is exactly the largest number of firings alive at one instant, and that peak can be found from the endpoints alone: sort the starts and the ends separately, then walk them together adding one at each start and subtracting one at each end.

The lower bound is plain: k firings alive at once need k kilns. The upper bound is what makes the sweep correct — walking the events in time order, a start only ever waits if every kiln already holds a live firing, so the peak count is also enough. Nothing needs to know which firing sits in which kiln, which is why the pairs can be broken apart.

Algorithm

1. Return 0 for an empty list.
2. Collect the start hours into one sorted list and the end hours into another.
3. Walk both with an index each, keeping a running count of live firings.
4. If the next end is at or before the next start, consume the end and drop the count by one; otherwise consume the start and raise the count by one.
5. Track the largest count ever seen and return it.

Complexity

Time O(n log n) for the two sorts; the walk is linear. Space O(n) for the endpoint lists.

Hours are capped at 10^4, so a counting version exists: keep an array of that length, add one at each start and subtract one at each end, prefix-sum it, and take the maximum. That is O(n + H) with no sort at all — the right choice while H stays comparable to n.

Solution

"""Kiln slots — sweep the sorted endpoints and keep the peak live count."""


def solve(firings):
    if not firings:
        return 0
    starts = sorted(start for start, _ in firings)
    ends = sorted(end for _, end in firings)

    live = peak = 0
    s = e = 0
    while s < len(starts):
        # invariant: `live` is the number of firings burning at the earlier of
        # the two pending events. Ends are consumed first at an equal hour,
        # because a kiln emptied at hour t is available at hour t.
        if ends[e] <= starts[s]:
            live -= 1
            e += 1
        else:
            live += 1
            s += 1
            peak = max(peak, live)
    return peak

TESTS = [
    (([[0, 6], [5, 9], [8, 12]],), 2),
    (([[2, 5], [5, 8], [8, 11], [11, 14]],), 1),
    (([[0, 4], [1, 5], [2, 6], [3, 7]],), 4),
    (([],), 0),
    (([[7, 19]],), 1),
    (([[3, 8], [3, 8], [3, 8]],), 3),
    (([[0, 100], [40, 50], [60, 70]],), 2),
]

Pitfalls

• Processing a start before an end at the same hour. The relay [[2, 5], [5, 8], [8, 11]] then reports 2 kilns instead of 1, because the sweep believes the second firing begins while the first is still burning.
• Insisting the sorted starts stay paired with their own ends. The i-th start usually does not belong to the i-th end, and it does not have to: the sweep only counts. Preserving the pairing is what pushes people back to the quadratic scan.
• Returning the final count instead of the running maximum. Every firing ends by the end of the week, so the count finishes at zero and every input answers 0.

Variants

• Irrigation windows — the same sorted sweep, but merging the overlaps rather than counting them.
• Lane bookings — the same peak count, reported after every new booking.