//problem description: merge K sorted lists with total N elements

//solution: put the front element of each list into a priority queue,

// till finish, pop the min value from the priority queue, and enqueue

// the next element in corresponding list, delete that element

//time complexity:

// select min value in the queue with K elements: O(lgK)

// repeat O(n) times

// time complexity = O(n * lgK)

//space complexity:

// output array = O(n)

// priority queue = O(k)

// space complexity = O(n + k) = O(n)

#include <queue>

#include <list>

#include <vector>

#include <iostream>

using namespace std;

//support compare function for priority heap

struct Comparator

{

bool operator()(const list<int>*a, const list<int>*b) const

{

if(b->size() == 0)

return false;

return a->front() > b->front();

}

};

vector<int> nWayMerge(list<list<int> >& l)

{

vector<int> output;

priority_queue<list<int>*, vector<list<int>* >, Comparator> q;

list<list<int> >::iterator iter;

//initialize the priority queue by

//putting each list

//into the queue

for(iter = l.begin(); iter != l.end(); iter++)

q.push(&*iter);

//once the min list goes empty,

//we know all elements has been dealed

while(q.top()->size() != 0)

{

//pop the min element in the queue

output.push_back(q.top()->front());

q.top()->pop_front();

list<int>* l = q.top();

q.pop();

q.push(l);

}

return output;

}

int main()

{

//test cases with 3 sorted lists

list<list<int> > input;

list<int> l1 = {12, 15, 16, 18, 20};

list<int> l2 = {11, 13, 18, 20, 22};

list<int> l3 = {9, 14, 15, 20, 23};

input.push_back(l1);

input.push_back(l2);

input.push_back(l3);

vector<int> v = nWayMerge(input);

for(vector<int>::iterator iter = v.begin(); iter != v.end(); iter++)

cout << *iter << endl;

return 0;

}