Challenge: Merge Sorted Lists

Lab C++ Intermediate 20 points

Read m sorted lists and merge them with a heap (don't just join and sort).

Input

Line 1: m. Then m lines: a length L followed by L sorted numbers (L ≥ 1).

Output

The merged list, separated by spaces.

Example

Input

Output

1 2 3 4 5 6 9 10

Sample input available Sample output available

Editor

C++

Hints

Start with (first value, list index, 0) for each list.

After popping, push the next value of the same list.

Solution explanation

The heap holds one item per list: O(N log m) for N numbers in m lists.

Show solution

#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;

int main() {
    int m;
    cin >> m;
    vector<vector<int>> lists(m);
    for (auto& l : lists) {
        int len;
        cin >> len;
        l.resize(len);
        for (int& x : l) cin >> x;
    }
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    for (int i = 0; i < m; i++) pq.push({lists[i][0], i, 0});
    vector<int> out;
    while (!pq.empty()) {
        auto [v, i, j] = pq.top();
        pq.pop();
        out.push_back(v);
        if (j + 1 < (int)lists[i].size()) pq.push({lists[i][j + 1], i, j + 1});
    }
    for (size_t k = 0; k < out.size(); k++) cout << out[k] << (k + 1 < out.size() ? " " : "\n");
    return 0;
}

Output

Answer