 How to solve this question
(Contest Page | CodeChef)

Read how to "merge K sorted arrays GFG "-

Code-

``````typedef pair<int, pair<int, int> > ppi;

// This function takes an array of arrays as an
// argument and all arrays are assumed to be
// sorted. It merges them together and prints
// the final sorted output.
vector<int> mergeKArrays(vector<vector<int> > arr)
{
vector<int> output;

// Create a min heap with k heap nodes. Every
// heap node has first element of an array
priority_queue<ppi, vector<ppi>, greater<ppi> > pq;

for (int i = 0; i < arr.size(); i++)
pq.push({ arr[i], { i, 0 } });

// Now one by one get the minimum element
// from min heap and replace it with next
// element of its array
while (pq.empty() == false) {
ppi curr = pq.top();
pq.pop();

// i ==> Array Number
// j ==> Index in the array number
int i = curr.second.first;
int j = curr.second.second;

output.push_back(curr.first);

// The next element belongs to same array as
// current.
if (j + 1 < arr[i].size())
pq.push({ arr[i][j + 1], { i, j + 1 } });
}

return output;
}
``````

Just read the concept of priority queue, Also the editorials have been published, it would be good for you to take a look at them. U will surely understand the solution