All problems

Shortest Head First

Medium · heap

A single machine serves k worker queues. Each queue is a linked list of task durations, and a queue's tasks must be served in the order they appear in that list. The durations in a queue are not sorted.

Whenever the machine is free it looks at the task at the head of every non-empty queue, picks the one with the smallest duration, runs it, and removes it from its queue. If two or more heads share the smallest duration, it takes the one from the queue with the lower index in queues.

Return one linked list holding the durations in the order the tasks were run.

Some queues can be empty, and queues itself can be empty. If there are no tasks at all, return None. Reusing the existing nodes is fine, you do not have to create new ones. The nodes you receive are ListNode objects with a val and a next.

Examples

Example 1

Input: queues = [[4, 2], [3, 5], [1]]

Output: [1, 3, 4, 2, 5]

The heads are 4, 3 and 1, so 1 runs. Then the heads are 4 and 3, so 3 runs. Then 4 and 5, so 4 runs, which exposes 2 at the front of the first queue. Then 2 runs and finally 5.

Example 2

Input: queues = [[2, 9], [2, 1]]

Output: [2, 2, 1, 9]

Both heads are 2, so the first queue goes first. Then the heads are 9 and 2, so the second queue's 2 runs, then its 1, and 9 comes last.

Example 3

Input: queues = []

Output: []

There are no queues, so no task is ever run.

Constraints