dsa · hard

Merge the Arrival Boards

An airport wall shows boards, a list of arrival boards. Each board is a list of flight numbers already sorted in non-decreasing order, and boards may have very different lengths. Consolidate every board into one master list, still in non-decreasing order, and return it.

Arguments

boards may be empty and individual boards may be empty; the master list of an all-empty wall is [].

Example

boards = [[1,4,7],[2,3,9],[5]]

Reading the smallest unclaimed number each pass: 1 (board 1), 2 (board 2), 3 (board 2), 4 (board 1), 5 (board 3), 7 (board 1), 9 (board 2) → [1,2,3,4,5,7,9].

boards = [[],[10]] → the empty board contributes nothing → [10].

Constraints

0 <= boards.length <= 10^4 0 <= boards[i].length <= 500 -10^4 <= boards[i][j] <= 10^4 each board is sorted in non-decreasing order Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
[[1,4,7],[2,3,9],[5]]

Expected:
[1,2,3,4,5,7,9]

Example 2

Input:
[[],[10]]

Expected:
[10]

Example 3

Input:
[]

Expected:
[]

Open in the Dojo editor