力扣 632 最小区间

题意：给定几个拍好序的list，找出一个最小的区间包含至少一个list中的元素

思路：

1. 用一个pair记录list的index和每一个list的index，
2. 然后创建一个最小堆，把每一个list的头节点加入最小堆，
3. 然后开始不停的poll最小堆的元素，
4. 同时把poll出的最小元素的对应的list中的下一个元素加入最小堆，
5. 同时更新堆中的最大值与最小值，并查看每次poll之后的最小最大值之差，是否比之结果中记录的结果小，
6. 如果小则更新结果

思想：队列

复杂度：时间O（nlgn)，空间O(n^2)

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue(new Comparator<Pair<Integer, Integer>>(){
            public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) {
                return nums.get(p1.getKey()).get(p1.getValue()) - 
                    nums.get(p2.getKey()).get(p2.getValue());
            }
        });
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int[] result = new int[2];
        for(int i=0;i<nums.size();i++) {
            pq.add(new Pair(i, 0));
            min = Math.min(nums.get(i).get(0), min);
            max = Math.max(nums.get(i).get(0), max);
        }
        result[0] = min; 
        result[1] = max; 
        while(true) {
            Pair<Integer, Integer> cur = pq.poll();
            int index2 = cur.getValue();
            int index1 = cur.getKey();
            if(index2+1 == nums.get(index1).size()) {
                break;
            }
            Pair<Integer, Integer> temp = new Pair(index1, index2+1);
            pq.add(temp);
            Pair<Integer, Integer> next = pq.peek();
            min = nums.get(next.getKey()).get(next.getValue());
            max = Math.max(max, nums.get(temp.getKey()).get(temp.getValue()));
            if(max - min < result[1] - result[0]) {
                result[0] = min;
                result[1] = max;
            }
        }
        return result;
    }
}