Use k-way merging +1.
1. Before the merging start, sorting these lists according to the
first element of each list. // O(k log k)
2. So the first element in the first list is the smallest element. Put
the smallest into the result array. // O(1)
3. Then, using binary search to find the new
I think this problem is a DP problem too.
Google Code Jam Round 1A has a similar problem in this year.
http://code.google.com/codejam/contest/dashboard?c=544101#s=p1
In the contest analysis page. It also explains the detail.
http://code.google.com/codejam/contest/dashboard?c=544101#s=aa=1
--
