请问一道google面试题： merge k sorted list with timestamp

面试google,碰到一道新题：
Given K sorted list, each list contains many (timestamp, key, value) entries sorted by key. 写一个基于iterator的merger function,把这些entries按照顺利合并。同一个（key, value)的entry, 比较timestamp, timestamp 大的覆盖带哦timestamp 小的。
面试时候给了一个近似以下的解法。但是只能排序合并，不能merge timestamp。
请问各位有好的解法没有？


public class Solution {
    public static Iterable<Integer> mergeKSortedIterators(List<Iterator<Integer>> iterators) {
        List<Integer> result = new ArrayList<>();
        if (iterators == null || iterators.size() == 0) {
            return result;
        }
         
        PriorityQueue<MyIterator> pq = new PriorityQueue<>(iterators.size());
         
        for (Iterator<Integer> iterator : iterators) {
            if (iterator.hasNext()) {
                pq.add(new MyIterator(iterator.next(), iterator));
            }
        }
         
        while (!pq.isEmpty()) {
            MyIterator curr = pq.poll();
            result.add(curr.val);
            if (curr.hasNext()) {
                pq.add(curr);
            }
        }
         
        return result;
    }

private static class MyIterator implements Comparable<MyIterator> {
        private Integer val;
        private Iterator<Integer> iterator;
         
        public MyIterator(Integer val, Iterator<Integer> iterator) {
            this.val = val;
            this.iterator = iterator;
        }
         
        public boolean hasNext() {
            if (iterator.hasNext()) {
                val = iterator.next();
                return true;
            }
            
            return false;
        }
         
        public int compareTo(MyIterator that) {
            return this.val - that.val;
        }
    }

public static void main(String[] args) {
        List<Integer> a = new ArrayList<>();
        a.add(1);
        a.add(3);
        a.add(5);
         
        List<Integer> b = new ArrayList<>();
        b.add(2);
        b.add(4);
         
        List<Iterator<Integer>> iterators = new ArrayList<>();
        iterators.add(a.iterator());
        iterators.add(b.iterator());
         
        Iterable<Integer> result = mergeKSortedIterators(iterators);
         
        for (Integer num : result) {
            System.out.println(num);
        }
    }
}

同志，你的算法是将所有元素一股脑塞进一个优先队列，然后按顺序取出来？
如果是这样的话，假设一共n元素，时间复杂度应当是nlogn，如果你的优先队列是用堆写的话。（事实上这不就是一个堆排序吗）
在此情况下，采用 平衡树作为优先队列， 以 (key, value) 作为 键，timestamp 作为值， 不停插入和更新平衡树， 最后做中序遍历输出

但是，这显然并不是最优的，因为你丢掉了每个初始队列都是有序的这一性质。
本题的名字也提示了我们，往归并排序上去想。
设想有k个指针分别指向k个队头，比较这k个指针指向元素，选择key最小的加进答案，相应的指针++
复杂度很好分析，因为每次必然选入一个元素，时间复杂度是 n*选择的代价

那么选择的代价是多少呢？naive的想法，k元素选最小的是O(k)
更好的算法，将这k个元素组成一个堆，选择堆顶元素是O(1)， 插入新元素是O(logk)

Mickeypeng 发表于 2019-2-23 22:17
同志，你的算法是将所有元素一股脑塞进一个优先队列，然后按顺序取出来？
如果是这样的话，假设一共n元素 ...

选择代价是 O(k) 吧，组成堆也至少是 O(k) 的

zhxiaog 发表于 2019-2-24 10:19
选择代价是 O(k) 吧，组成堆也至少是 O(k) 的

当然不是了

Mickeypeng 发表于 2019-2-24 13:48
当然不是了

仔细想了下，确实是 O(k)，多谢了

补充内容 (2019-2-24 16:10):
应该是 O(logk)，上面写错了，手误

Mickeypeng 发表于 2019-2-23 22:17
同志，你的算法是将所有元素一股脑塞进一个优先队列，然后按顺序取出来？
如果是这样的话，假设一共n元素 ...

因为考虑到楼顶“比较timestamp, timestamp 大的覆盖带哦timestamp 小的”，所以从PQ中拿出来的那个sorted list后应该不停的移动指针直到该sorted list指针指向不是该key的，再把它加回PQ。同时，PQ的顶部如果peek出来也是同样的key，也要重复此操作。知道PQ的顶部peek出来不是同样的key。这时返回最大的timestamp的value。

整体复杂度是O(N * Log K)

Mickeypeng 发表于 2019-2-23 22:17
同志，你的算法是将所有元素一股脑塞进一个优先队列，然后按顺序取出来？
如果是这样的话，假设一共n元素 ...

有道理，所以k 比较小的话就直接几个if else 判断累加指针咯

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](ListNode*& a, ListNode*& b) {
            return a->val > b->val; //最小堆
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp) > q(cmp);
        for (auto node : lists) {
            // 入堆排序
            if (node) q.push(node);
        }
        ListNode *dummy = new ListNode(-1), *cur = dummy;
        while (!q.empty()) {
            // 出堆
            auto t = q.top();
            q.pop();
            // 作为下一个节点
            cur->next = t;
            cur = cur->next;
            if (cur->next) {
                // 取下一个入堆
                q.push(cur->next);
            }
        }
        return dummy->next;
   
        
    }
}

主要这种思路如下：
初始化 将每个链表头入优先级队列
后续操作就是从队列中取出最小的元素，再将这个最小元素下一个节点入队列  
这样每次操作时间复杂O(log(k))  
整体复杂度是 nO(log(k))   
如果全部入队列是  nO(log(n))