Screen-print rotation

One press, several colour screens, and a wash line that will not be hurried. How many cycles does the run take once the waiting is counted?

The problem

A shirt shop runs a single press. Every print job needs one colour screen, and each cycle of the press either runs one job or sits idle. The moment a screen comes off the press it goes to the wash line for gap cycles, and it can be mounted again only on the cycle after that. Screens are independent — while indigo dries, ochre can run.

Jobs are interchangeable and may be run in any order, and an idle cycle costs the same as a printing one. Find the fewest cycles that finish every job.

Input. jobs — a list of strings, the screen each job needs. gap — an integer, the number of cycles a screen spends on the wash line.

Output. The smallest number of press cycles that completes all of jobs.

Example.

jobs = ["indigo", "indigo", "indigo", "ochre", "ochre", "ochre"], gap = 2  ->  8

Indigo, ochre, idle, indigo, ochre, idle, indigo, ochre. Two colours cannot fill a three-cycle window, so the press idles twice.

A second example, where the waiting disappears:

jobs = ["indigo", "indigo", "ochre", "sage", "teal", "rust"], gap = 2  ->  6

Indigo is busiest with two jobs, but four other screens can fill the window between them, so nothing idles and the answer is the number of jobs.

Constraints.

• 0 <= len(jobs) <= 10^4
• 0 <= gap <= 100
• each screen name is 1 to 12 lowercase letters

Hints

Approach

Brute force

Try every ordering of the jobs and keep the shortest schedule that respects the wash time. That is n factorial orderings — unusable past about ten jobs.

The insight

At every cycle, running the available screen with the most jobs left is never worse than any other choice, so the whole schedule falls out of one repeated "give me the largest count" query.

The busiest screen is the one still demanding the press last, and every cycle it does not run is one it may have to wait out at the end. Swap two adjacent choices in any optimal schedule so the busier screen goes first, and the schedule never gets longer. Repeated largest-first extraction with cheap updates is a max-heap; the wash line is a plain queue, because screens return in the order they left.

Algorithm

1. Count how many jobs each screen has. Push the counts into a max-heap.
2. Keep a queue of (cycle_available, remaining_count) for washing screens.
3. Each cycle, move every screen whose availability cycle has arrived back into the heap.
4. If the heap is non-empty, pop the largest count and run that screen; if work remains, queue it with availability cycle + gap + 1. Otherwise idle.
5. Stop when heap and queue are both empty; the cycle count is the answer.

Complexity

Time O(C log k), for C cycles in the answer and k distinct screens — each cycle does one pop and at most a few pushes. Space O(k), heap and wash queue together.

Solution

"""Screen-print rotation — greedy max-heap plus a cooldown queue."""

import heapq
from collections import Counter, deque


def solve(jobs, gap):
    if not jobs:
        return 0

    # Only the counts matter, never which screen is which.
    ready = [-count for count in Counter(jobs).values()]
    heapq.heapify(ready)
    washing = deque()                     # (cycle it may run again, -remaining)

    cycle = 0
    # Invariant: every screen with work left sits in exactly one of the two
    # structures — ready if it may run now, washing if it may not.
    while ready or washing:
        cycle += 1
        while washing and washing[0][0] <= cycle:
            heapq.heappush(ready, washing.popleft()[1])
        if ready:
            remaining = heapq.heappop(ready) + 1   # one job of this screen done
            if remaining:                          # still work left: send to wash
                washing.append((cycle + gap + 1, remaining))
    return cycle

TESTS = [
    ((["indigo", "indigo", "indigo", "ochre", "ochre", "ochre"], 2), 8),
    ((["indigo", "indigo", "ochre", "sage", "teal", "rust"], 2), 6),
    ((["indigo", "indigo", "indigo", "ochre"], 2), 7),
    ((["indigo", "indigo", "indigo", "ochre", "ochre", "ochre", "sage"], 2), 8),
    ((["ochre", "ochre", "ochre"], 0), 3),
    ((["indigo", "indigo", "indigo", "indigo"], 3), 13),
    (([], 3), 0),
    ((["gold"], 5), 1),
]

Pitfalls

• Queueing a screen whose count has reached zero. The finished screen keeps reappearing and the loop never ends. Re-queue only while work remains.
• Using availability cycle + gap rather than cycle + gap + 1. A screen run on cycle 1 with gap = 2 returns on cycle 4, not 3, and every run that idles comes back a cycle short.
• Running whichever screen is ready rather than the busiest one. With three indigo jobs, three ochre and one sage at gap = 2, opening with sage costs 9 cycles; opening with a busy screen costs 8.

Variants

• Back-to-back on air — the same largest-count-first greedy, but it returns the arrangement rather than its length.
• Tug-of-war ladder — repeated extract-max where the result of each step is pushed back into the same heap.