A single CPU processes jobs one at a time. Given the queue of pending jobs and how long each one takes, implement schedule(tasks), which decides the order to process them in.

Input

tasks = [("A", 3), ("B", 1), ("C", 2)]

• Each entry is a (task name, duration) pair.
• Durations are integers of 0 or more.
• The same task name may appear more than once.

Output

Return a list of tuples in the same shape as the input, in execution order.

schedule([("A", 3), ("B", 1), ("C", 2)])
# [("B", 1), ("C", 2), ("A", 3)]

That is the shortest duration first. B takes 1 and goes first, C takes 2 and comes next, A takes 3 and goes last. A was at the front of the input, but that has no bearing on the execution order.

The sort order

Compare on two levels.

1. Duration ascending. Shorter jobs are processed first.
2. If durations tie, task name ascending.

Running the shortest job first is the rule known as SJF (Shortest Job First). Putting a long job up front makes every job behind it wait that much longer, so this ordering minimizes the average wait time.

Compare names with Python's default string comparison. It follows character codes, so uppercase sorts before lowercase. Between "apple" and "Banana" at equal duration, "Banana" comes first.

Things to watch

1. Duration is always the primary key. A job named "z" with duration 1 still comes before "a" with duration 9.
2. A duration of 0 is a valid value, and such a job is processed first.
3. If two entries have both the same name and the same duration, both stay in the result. Duplicates are not removed.
4. Empty input returns an empty list.

Implement schedule(tasks). The same task name may appear more than once.