#include <iostream>
#include <vector>
#include <queue>

using namespace std;
// k = number of lists
// N = number of elements
// n_k = number of element in list k

// What happens if every list is not sorted?
// O(NlogN) if I merge all vectors and I sort them
// O(Nlogk) + O(N*log(N/k)) -> O(NlogN) if I sort all vectors and do heaps and I merge them

// What happens if every list is sorted?
// O(NlogN) if I merge all vectors and I sort them
// O(Nlogk) if I take the min every time with heaps and I merge them
// O(Nk) if I take the min every time without using heaps and I merge them <-

struct Element {
    int val;
    int index;
    Element(int val, int index) : val(val), index(index) {};
};

struct Compare {
    bool operator() (const Element& e1, const Element& e2) {
        return(e1.val > e2.val);
    }
};

void PrintVector(const vector<Element>& nums) {
    for (Element num : nums)
        std::cout << num.val << " ";

    std::cout << std::endl;
}

// O(Nlogk)
vector<int> MergeKVectors(const vector<vector<int>>& lists) {

    vector<Element> elements;
    elements.reserve(lists.size());
    for (int i = 0; i < lists.size(); ++i) {
        if (!lists[i].empty()) {
            Element new_element(lists[i][0], i);
            elements.emplace_back(new_element);
        }
    }

    // O(k)
    priority_queue<Element, vector<Element>, Compare> pq(elements.begin(), elements.end());

    vector<int> solution;
    vector<int> positions(lists.size(), 0);

    // O(Nlogk)
    while (!pq.empty()) {
        Element current = pq.top();
        solution.emplace_back(current.val);
        ++positions[current.index];

        // O(logk)
        pq.pop();

        if (positions[current.index] < lists[current.index].size()) {
            Element next(lists[current.index][positions[current.index]], current.index);
            // O(logk)
            pq.push(next);
        }
    }

    return solution;
}

void PrintVector(const vector<int>& nums) {
    for (int num : nums)
        std::cout << num << " ";

    std::cout << std::endl;
}

int main()
{
    vector<vector<int>> lists{{1, 2, 4}, {3}, {1, 5}, {0}};

    vector<int> sorted_list = MergeKVectors(lists);

    PrintVector(sorted_list);

    return 0;
}