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

We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-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].

Note:

The given list may contain duplicates, so ascending order means >= here.

1 <= k <= 3500

-105 <= value of elements <= 105.

For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.

• [x] 和merge k sorted list一个思路
• [x] Image you are merging k sorted array using a heap. Then everytime you pop the smallest element out and add the next element of that array to the heap. By keep doing this, you will have the smallest range.

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<Element> queue = new PriorityQueue<>(nums.size(), (a, b) -> (a.val - b.val));
        int curtMax = 0;
        int range = Integer.MAX_VALUE;
        //when the diff is max, this is the range 
        //we want to find the smallest range

        for(int i = 0; i < nums.size(); i++) {
            if (nums.get(i) != null || nums.get(i).size() >= 1) {
                Element e = new Element(nums.get(i).get(0), 0, i);
                queue.offer(e);
                curtMax = (curtMax < nums.get(i).get(0)) ? nums.get(i).get(0) : curtMax;
            }

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

        int start = 0;
        int end = 0;
        int diff = 0;
        while (queue.size() == nums.size()) {
            Element head = queue.poll();
            /***************************************//***************************************/

            if (curtMax - head.val < range) {
                range = curtMax - head.val;
                start = head.val;
                end = curtMax;
            } 

            /***************************************//***************************************/
            if (head.index + 1 < nums.get(head.row).size()) {

                Element newE = new Element(nums.get(head.row).get(head.index+1), head.index + 1, head.row);
                queue.offer(newE);
                if (newE.val > curtMax) {
                    curtMax = newE.val;
                } 
            }
         }
        return new int[]{start, end};


    }
    private class Element {
        int val;
        int index;
        int row;
        private Element(int val, int index, int row) {
            this.val = val;
            this.index = index;
            this.row = row;
        }
    }
}