Standard Bar Heaps · Medium Problems O(K^2 log K) · O(K)
An immigration hall runs k serving lanes, each already ordered from fastest to slowest applicant. The control desk must interleave all lanes into one master queue, always pulling the next-fastest applicant overall. The desk keeps a shortlist of each lane's current head, promotes the overall leader, and refills that lane's slot from its next applicant.
Input: A matrix of K rows, each a sorted array of K values, and the integer K.
Output: Return one sorted array containing all K*K values.
1 <= K <= 10^2-10^9 <= values <= 10^9Each row is sorted in non-decreasing orderInput: {"matrix":[[1,5,9],[2,6,10],[3,7,11]],"K":3}
Output: [1,2,3,5,6,7,9,10,11]
The heap interleaves the three lanes by their current heads.
Input: {"matrix":[[1,3],[2,4]],"K":2}
Output: [1,2,3,4]
Two lanes alternate cleanly until both are drained.