Back-to-back on air
Order a request queue so the same act never plays twice in a row, by always taking the act with the most tracks still waiting.
A community station has a pile of listener requests and one rule from the producer: never play the same act twice in a row. Some piles cannot obey it.
The problem
The overnight show has a queue of requests, each naming the act whose track is wanted. Every request must be played exactly once, in any order the presenter likes, and no two consecutive slots may name the same act. Produce such an order, or report that none exists. To keep the answer unique: when two acts have the same number of tracks still waiting, the one whose name comes first alphabetically goes on air first.
Input. requests — a list of strings, the act named by each request.
Output. A list holding the same requests in a legal order, or an empty list if no legal order exists.
Example.
requests = ["kite", "kite", "moor", "dune"] -> ["kite", "dune", "kite", "moor"]
Kite has two tracks and goes first; dune and moor are tied on one each, so dune takes the second slot and splits the kite pair.
A second example, where the pile cannot be saved:
requests = ["kite", "kite", "kite", "moor"] -> []
Four slots, three of them kite. Even at slots one, three and four, two kites touch — an act holding more than half the slots can never be spread out.
Constraints.
0 <= len(requests) <= 10^5- each act name is 1 to 16 lowercase letters
- an empty queue has one legal order: the empty one
Hints
Hint 1
Only the counts matter. Try small piles by hand and find the condition that makes one hopeless.
Hint 2
Think about the act with the most requests. Delay it and its tracks pile up behind you; there is never a reason to play a rarer act first.
Hint 3
The act you just played is the only one banned from the next slot. Hold it outside the heap for exactly one round, then put it back.
Approach
Brute force
Generate permutations and return the first with no repeated neighbours. A 12-request queue is already 479 million orderings, and the limit is 10⁵.
The insight
Playing the act with the most tracks still waiting is always safe, because the only act that can strand you at the end is the one you kept postponing.
If an act holds at most half the slots, rounded up, it can be spread out; otherwise two of its tracks must touch by the pigeonhole principle. Taking the largest count first keeps the counts level, so no act grows into that majority. The one restriction is that the act just played cannot repeat, so hold it aside for a single round — it is the only entry the heap must not offer, and one slot later it is legal again.
Algorithm
- Count the requests per act and push
(-count, name)onto a heap. Negating the count gives largest-first, and the name settles ties alphabetically. - Pop the top entry, append its name to the schedule, and decrement its count.
- Push back the entry held from the previous round, if there was one.
- Hold this round's entry aside if it still has tracks left; drop it otherwise.
- Repeat until the heap empties. If the schedule is shorter than the queue, the held entry never found a slot: return an empty list.
Complexity
Time O(n log k), for n requests and k distinct acts — one pop and at most one push per slot. Space O(k) for the heap and counts, plus the schedule.
Solution
"""Back-to-back on air — max-heap by tracks left, with the last artist held out one slot."""
import heapq
from collections import Counter
def solve(requests):
if not requests:
return []
# (-tracks left, artist): the heap orders by most work first, then by name,
# so ties resolve alphabetically and the schedule is unique.
pool = [(-tracks, artist) for artist, tracks in Counter(requests).items()]
heapq.heapify(pool)
schedule = []
held = None # artist just played: ineligible for this slot
while pool:
tracks, artist = heapq.heappop(pool)
schedule.append(artist)
if held: # the previous artist is clear again
heapq.heappush(pool, held)
tracks += 1 # one of this artist's tracks is now on air
held = (tracks, artist) if tracks else None
# A held artist with tracks left and an empty pool means no legal slot was
# ever free for them, so no arrangement exists at all.
return schedule if len(schedule) == len(requests) else []The cases that ran
TESTS = [
((["kite", "kite", "moor", "dune"],), ["kite", "dune", "kite", "moor"]),
((["kite", "kite", "kite", "moor"],), []),
((["ferrow", "ferrow", "ferrow", "dune", "dune", "kite"],),
["ferrow", "dune", "ferrow", "dune", "ferrow", "kite"]),
((["kite", "kite", "moor"],), ["kite", "moor", "kite"]),
((["kite", "kite"],), []),
((["kite"],), ["kite"]),
(([],), []),
]Pitfalls
- Pushing the held entry back before popping the next one. It goes straight
back to the top and plays twice in a row:
["kite", "kite", "moor"]comes out as["kite", "kite", "moor"]with no complaint. - Holding an act whose count has reached zero. It returns to the heap, gets popped again, and its stored count climbs instead of falling — the loop never ends.
- Returning the schedule without the length check. An impossible pile such as
["kite", "kite", "kite", "moor"]produces a short but legal-looking list instead of the empty list the problem asks for.
Variants
- Screen-print rotation — the same hold-aside greedy with a gap of one, counting slots instead of naming them.
- Tug-of-war ladder — a heap whose entries change value between rounds rather than being held out.