Given_k_sorted integer arrays, merge them into one sorted array.

Have you met this question in a real interview?

Yes

Example

Given 3 sorted arrays:

[
  [1, 3, 5, 7],
  [2, 4, 6],
  [0, 8, 9, 10, 11]
]

return[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].

Challenge

Do it in O(N log k).

• N is the total number of integers.
• k is the number of arrays.

class Solution {
public:
    /**
     * @param arrays k sorted integer arrays
     * @return a sorted array
     */
    vector<int> mergekSortedArrays(vector<vector<int>>& arrays) {
        // Write your code here
        vector<int> res;
        priority_queue<Node, vector<Node>, NodeCmp> heap;
        for (int i = 0; i < arrays.size(); ++i) {
            if (!arrays[i].empty()) {
                auto node = Node(i, 0, arrays[i][0]);
                heap.push(node);
            }
        }
        while (!heap.empty()) {
            auto node = heap.top();
            heap.pop();
            res.push_back(node.val);
            if (node.col + 1 < arrays[node.row].size()) {
                ++node.col;
                node.val = arrays[node.row][node.col];
                heap.push(node);
            }
        }

        return res;
    }

private:
    struct Node {
        Node(int _row, int _col, int _val):
            val(_val), row(_row), col(_col){}
        int val, row, col;
    };

    struct NodeCmp {
        bool operator() (Node &left, Node &right) {
            return left.val > right.val;
        }
    };
};