Q3 - Thermal-Safe Cell Discharge Scheduling

Scenario: A Tesla battery pack meets a power demand by discharging its cells in sequence. Each discharge heats a cell, so for thermal safety a cell that just discharged must rest for a fixed number of cycles before it can discharge again. You are given a batch of discharges to run (some cells appear several times) and the required cooldown.

Part 1: Given cells (the batch, each entry a cell id) and cooldown, return an ordering that runs every discharge back to back while keeping any two discharges of the same cell at least cooldown + 1 slots apart. If no such ordering exists, return an empty list. Any valid ordering is accepted.

Input:  cells = ["A", "A", "A", "B", "B", "C"], cooldown = 1
Output: ["A", "B", "A", "B", "A", "C"]
Why: the three A discharges land at slots 0, 2, 4, always 2 apart (cooldown 1
        means a 1-cycle rest, so the same cell must be at least 2 slots apart).

Input:  cells = ["A", "A", "A", "B"], cooldown = 2
Output: []
Why: A needs its three discharges 3 slots apart: slots 0, 3, 6. But only 4 slots
        exist and just one non-A cell, so the third A cannot be spaced out. No ordering works.

Part 1: Greedy, Newest-Rest-Last

Two facts drive the solution. First, to finish as tightly as possible you should always spend the most-used cell that is legal right now, because falling behind on the busiest cell is what makes a schedule impossible. Second, a cell you just used is illegal for exactly cooldown slots, so a short first-in-first-out queue can hold resting cells and release them right when they are legal again.

Step 1: Count the discharges per cell

Tally how many times each cell must discharge. This tells you which cell is the bottleneck and how many are tied for busiest.

cells = [A, A, A, B, B, C]
remaining = { A: 3, B: 2, C: 1 }      A is the busiest cell

Step 2: At each slot, spend the busiest free cell

Walk the schedule slot by slot. Look at every cell that still has discharges left and is not resting, and pick the one with the largest remaining count. Place it, drop its count by one, and send it to rest.

remaining = { A: 3, B: 2, C: 1 },  nobody resting
slot 0:  A and B and C are free.  A has the most (3).  ->  place A
         remaining = { A: 2, B: 2, C: 1 },  A now resting
slot 1:  A is resting.  B has the most among the free (2).  ->  place B

best = None
for cell, count in remaining.items():
    # only a cell with discharges left and not currently resting can be placed
    if count > 0 and cell not in resting and (best is None or count > remaining[best]):
        best = cell

Step 3: Release cells from the cooldown queue

Push each placed cell onto a queue of resting cells. Once that queue holds more than cooldown cells, the one at the front has rested long enough, so pop it and mark it free again. If a slot arrives where no cell is both free and unfinished, the batch cannot be scheduled and you return empty.

cooldown = 1  ->  the rest queue may hold 1 cell; a 2nd push frees the oldest

place A (slot 0):  cooling = [A]
place B (slot 1):  cooling = [A, B]  ->  over the limit, free A   ->  A is legal at slot 2

cooling.append(best)
resting.add(best)
if len(cooling) > cooldown:            # the oldest resting cell has cooled off
    resting.discard(cooling.popleft())

Here is the whole sweep on Example 1, slot by slot. Watch the busiest cell A stay in motion while B and C fill the gaps, and how a placed cell is always resting on the very next slot:

1 / 7

# O(n * k) time | O(k) space  (n discharges, k distinct cells)
from collections import Counter, deque

def schedule(cells, cooldown):
    remaining = Counter(cells)
    order = []
    cooling = deque()                      # cells resting, oldest first
    resting = set()                        # fast "is this cell resting?" lookup
    while len(order) < len(cells):
        # pick the free cell with the most discharges left
        best = None
        for cell, count in remaining.items():
            if count > 0 and cell not in resting and (best is None or count > remaining[best]):
                best = cell
        if best is None:
            return []                      # a discharge is due but every cell is resting: impossible
        order.append(best)
        remaining[best] -= 1
        cooling.append(best)
        resting.add(best)
        if len(cooling) > cooldown:        # the oldest resting cell has cooled off
            resting.discard(cooling.popleft())
    return order

Part 2: When Rest Cycles Are Allowed

Part 2: Suppose the pack may insert idle cycles where nothing discharges (the pack simply rests). Now a schedule always exists. Return the minimum total number of cycles, discharges plus any idles, to complete every discharge while respecting the cooldown.

Input:  cells = ["A", "A", "A", "B"], cooldown = 2
Output: 7
Why: A must sit 3 apart: slots 0, 3, 6. B fills one gap, the other two are idle:
        A B _ A _ _ A  ->  7 cycles.  (Back to back was impossible, so we pay 3 idle cycles.)

Only the busiest cell matters. If a cell appears maxFreq times, it forces maxFreq - 1 gaps, and each gap is a full cooldown + 1 cycles wide (the discharge plus its rest). That builds a skeleton of (maxFreq - 1) * (cooldown + 1) cycles; then the final, most-frequent discharges land in one last row, one cycle per cell that ties for busiest. Every other cell tucks into the idle gaps for free. The only way the answer can grow beyond that skeleton is if there are simply so many discharges that they cannot all fit, so take the larger of the two.

cells = [A, A, A, B],  cooldown = 2
maxFreq = 3 (A),  cells tied for busiest = 1

skeleton:  A _ _  A _ _  A     = (3 - 1) * (2 + 1) + 1 = 7
fill gaps: A B _  A _ _  A     total = max(4, 7) = 7

# O(n) time | O(k) space
from collections import Counter

def min_total_time(cells, cooldown):
    if not cells:
        return 0
    counts = Counter(cells)
    max_freq = max(counts.values())
    num_busiest = sum(1 for count in counts.values() if count == max_freq)
    # the busiest cell forces (max_freq - 1) gaps of (cooldown + 1), then a final row of the ties
    return max(len(cells), (max_freq - 1) * (cooldown + 1) + num_busiest)

Common Pitfalls

• Not always spending the busiest cell. If you place a lighter cell while the busiest one is free, the busiest cell falls behind and a solvable batch can look impossible. Greedy on the highest remaining count is what guarantees correctness.
• Getting the cooldown window off by one. A cooldown of c means the same cell must be c + 1 slots apart, so the rest queue holds cells for exactly c slots. Releasing one slot too early or too late breaks the spacing.
• Forgetting the impossible case. In Part 1 there is no idle, so if every unfinished cell is resting at some slot, no schedule exists. Detect it and return empty rather than looping forever.
• Over-counting in Part 2. The answer is driven by the busiest cell's gaps, not the total. Only when the batch is large enough to overflow those gaps does the raw length win, which is why the answer is the max of the two.

Complexity Analysis

Part 1: O(n * k) time, where n is the number of discharges and k the number of distinct cells: each of the n slots scans the k cells to find the busiest free one. A max-heap keyed by remaining count would trim the pick to O(log k), giving O(n log k), but with few distinct cells the plain scan is simpler and just as fast. Space is O(k) for the counts, the rest queue, and the resting set.

Part 2: O(n) time to tally the counts and read off the busiest, O(k) space. No scheduling needed: the closed-form skeleton gives the answer directly.

Final Notes

1. The busiest cell is the bottleneck. Its count sets the shape of every answer here. Saying that out loud first, then building the schedule around it, is most of the insight.
2. Greedy on highest remaining count is provably right. Always spending the most-used legal cell never traps you: if any valid schedule exists, this one finds it. Being able to state that confidently is what separates a guess from a solution.
3. A short queue is the cooldown. Holding placed cells for exactly cooldown slots, then releasing the oldest, enforces the spacing in O(1) per slot with no scanning back over the schedule.
4. Part 2 needs no scheduling at all. Once you see that the busiest cell forces (maxFreq - 1) full gaps plus a final row, the minimum time is a formula, and the raw length only matters when the batch overflows those gaps.
5. Name the family. This is the "rearrange with a gap constraint" pattern (the same shape as task scheduling with cooldown). Recognizing it means you can adapt it the moment the constraint changes. 🚀