← All Problems

31. Schedule Tickets with Cooldown

General Pattern Medium Greedy — Task Scheduler
Grounding: Note: general algorithmic pattern relevant to conversational-AI/support-ops engineering; not a confirmed detail of Fin's specific implementation.

Problem

Fin routes a batch of tickets to a human agent queue, one ticket type at a time. To stop an agent from grinding the same repetitive issue back-to-back, the same ticket type can't be handled twice within cooldown time slots of each other.

Given the sequence of ticket types that need to be handled (the scheduler is free to reorder them however it likes) and the cooldown, find the minimum number of time slots needed to get through all of them. Idle slots are allowed if nothing eligible is ready yet. This is the classic Task Scheduler problem (LeetCode 621).

Source: src/31_schedule_tickets_with_cooldown.py

def min_schedule_time(ticket_types: list[str], cooldown: int) -> int:

>>> min_schedule_time(["A", "A", "A", "B", "B", "B"], cooldown=2)
8
>>> min_schedule_time(["A", "A", "A", "A"], cooldown=2)
10

Step-by-Step Approach

  1. Count how many times each ticket type appears (a frequency table).
  2. Find max_freq, the highest count belonging to any single ticket type.
  3. Find count_max, the number of distinct ticket types that share that max count.
  4. Picture laying out max_freq "blocks" of the most frequent type, spaced cooldown + 1 slots apart, with the other max-frequency types filling the last block alongside it. That skeleton has (max_freq - 1) * (cooldown + 1) + count_max slots.
  5. Every other, less-frequent ticket type can always be slotted into the gaps of that skeleton without forcing extra idle time — so the skeleton size is a hard lower bound once there are enough total tickets to fill it.
  6. The true answer is never smaller than just the total number of tickets (you can't process more than one per slot), so take the max of the skeleton formula and len(ticket_types).

The key insight is that only the most frequent ticket type(s) can force idle slots — once you've spaced those out with the required cooldown, every less-frequent type has enough "room" to slot into the gaps for free, so you never need to simulate slot by slot.

Reference solution

from collections import Counter


def min_schedule_time(ticket_types: list[str], cooldown: int) -> int:
    # max-frequency-bucket formula (LC621), O(n) time, O(k) space, k = distinct types
    if not ticket_types:
        return 0
    # per-type counts, keys not needed
    freqs = Counter(ticket_types).values()
    # highest count among all ticket types
    max_freq = max(freqs)
    # how many types tie for max
    count_max = sum(1 for f in freqs if f == max_freq)
    # skeleton vs raw count
    return max(len(ticket_types), (max_freq - 1) * (cooldown + 1) + count_max)

Key Functions & Tricks

  • collections.Counter(iterable) — item-to-count mapping built in one pass, O(n).
  • Counter.values() — counts-only view, ignoring the keys.
  • max(freqs) — highest raw count across all ticket types.
  • sum(1 for f in freqs if f == max_freq) — generator-sum idiom for counting ties at the max.
  • max(len(ticket_types), (max_freq - 1) * (cooldown + 1) + count_max) — cooldown-block skeleton size vs raw ticket count, O(1).

How to Recognize This Pattern

Signals: "process items one at a time," "the same item can't repeat within K slots/steps," and the question asks for the minimum total time/slots rather than an explicit valid ordering. That combination is almost always the Task Scheduler frequency-bucket formula, not a simulation problem — resist the urge to actually build the schedule with a heap or queue unless the interviewer explicitly wants the ordering, not just the count. Variations: (1) a version with multiple cooldowns per item type simultaneously, and (2) a version that asks you to also produce the actual schedule (in which case a max-heap + cooldown queue simulation is the right tool, since the formula alone doesn't construct an ordering). A common pitfall is forgetting the max(len(ticket_types), ...) lower bound — when frequencies are close to uniform, the bucket formula alone can undercount, since idle slots aren't actually needed.

← Previous Next →