Task order with ties alphabetical

You work on the packing station of a parcel-delivery app. Packing a parcel is a list of tasks with names, such as box, pad and seal. Some tasks must be done before others: the box is built before it is padded.

The station screen shows one task at a time. When several tasks are ready, the screen shows the one whose name comes first in the alphabet, so every worker sees the same list. If the rules loop, no list exists.

Example 1 (traced)#

Input:  tasks = ["seal", "box", "pad", "label", "weigh"], firsts = ["box", "box", "pad", "seal"], thens = ["pad", "weigh", "seal", "label"]
Output: ["box", "pad", "seal", "label", "weigh"]

Pad and weigh both need box. Seal needs pad, and label needs seal. Kahn's algorithm keeps the ready tasks in a heap ordered by name.

Weigh was ready from round 2, but its name comes after the others, so it goes last.

Example 2#

Input:  tasks = ["fold", "tape"], firsts = ["fold", "tape"], thens = ["tape", "fold"]
Output: []

Fold must come before tape, and tape before fold. Neither can start, so no order exists.

Example 3#

Input:  tasks = ["tape", "box", "pad"], firsts = [], thens = []
Output: ["box", "pad", "tape"]

No rules. Every task is ready, and the screen shows them alphabetically.

• 1 ≤ len(tasks) ≤ 100,000, and every name is 1 to 10 lowercase letters, all different
• len(firsts) = len(thens), at most 100,000, and every name in them is in tasks
• A rule never links a task to itself, and the same rule can appear more than once.