You haveklists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of theklists.

We define the range [a,b] is smaller than range [c,d] ifb-a < d-cora < cifb-a == d-c.

Example 1:

Input:
[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]

Output:
 [20,24]

Explanation:

List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Solution: 类似于merge k sorted array，维持size为list.size()的min heap。每次放入一个元素时，更新max，每次弹出一个min时，看max - min是否少于range，如果是则更新start和end

    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<Pair> pq = new PriorityQueue<>(1, new Comparator<Pair>() {
            public int compare(Pair a, Pair b) {
                return a.val - b.val;
            }
        });
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            int val = nums.get(i).get(0);
            pq.offer(new Pair(i, 0, val));
            max = Math.max(max, val);
        }
        int start = -1, end = -1, range = Integer.MAX_VALUE;
        while (pq.size() == nums.size()) {
            Pair cur = pq.poll();
            if (max - cur.val < range) {
                start = cur.val;
                end = max;
                range = end - start;
            }
            if (cur.y + 1 < nums.get(cur.x).size()) {
                int val = nums.get(cur.x).get(cur.y + 1);
                pq.offer(new Pair(cur.x, cur.y + 1, val));
                max = Math.max(max, val);
            }
        }
        return new int[]{start, end};
    }
    class Pair {
        int val, x, y;
        public Pair(int x, int y, int val) {
            this.val = val;
            this.x = x;
            this.y = y;
        }
    }