struct Solution {}
use std::cmp::Ordering;
use std::collections::BinaryHeap;

#[derive(Clone, Eq, PartialEq)]
struct Element(Vec<i32>, usize); //第一个元素是数组本身,第二个则是他的编号
impl Ord for Element {
    fn cmp(&self, other: &Self) -> Ordering {
        other
            .0
            .get(0)
            .expect("self must have one element")
            .cmp(self.0.get(0).expect("other must have one element"))
    }
}
impl PartialOrd for Element {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
impl Solution {
    pub fn smallest_range(nums: Vec<Vec<i32>>) -> Vec<i32> {
        let mut nums = nums;
        let mut h = BinaryHeap::new();

        let k = nums.len();
        let mut current_max = std::i32::MAX;
        let mut range_start = -1;
        let mut range_end = -1;
        //对应的某个数组是否已经移除了一个数到q中
        let mut k_cnt: Vec<i32> = Vec::with_capacity(nums.len());
        //元素值以及其对应的数组下标
        let mut q: Vec<(usize, i32)> = Vec::new();
        let mut over = Vec::with_capacity(nums.len());

        //初始化队列,放入所有的数组
        for n in nums.iter_mut().enumerate() {
            if n.1.len() <= 0 {
                return vec![range_start, range_end]; //不可能满足条件,因为初始就有数组是空的
            }
            //怎么移出呢?
            h.push(Element(n.1.clone(), n.0));
            k_cnt.push(0);
            over.push(false);
        }
        /*
        1,2,3,4,5,6这些步骤才开始
        */
        let mut current_cnt = 0; //初始k_cnt中已经填充满了有效值
        while h.len() > 0 {
            let mut v = h.pop().expect("h must have one");
            let min = v.0.remove(0);
            let ke = k_cnt.get_mut(v.1).expect("must have");
            if *ke == 0 {
                //第一次找到了这个位置上的元素
                current_cnt += 1;
            }
            *ke += 1;
            q.push((v.1, min));
            if v.0.len() == 0 {
                //某一个数组遍历完了,还不能结束要等到最后一个元素使用完了才能结束
                over[v.1] = true;
            } else {
                h.push(Element(v.0, v.1));
            }
            //已经满足条件,那么移动left,直到
            if current_cnt == k {
                let mut min = q[0];
                let max = q[q.len() - 1];
                while current_cnt == k {
                    let first = q.remove(0);
                    k_cnt[first.0] -= 1;
                    if k_cnt[first.0] == 0 {
                        //某个数组降到了0,再讲就不满足目标了.
                        min = first;
                        current_cnt -= 1;
                    }
                }
                if max.1 - min.1 < current_max {
                    current_max = max.1 - min.1;
                    range_start = min.1;
                    range_end = max.1;
                }
            }
        }

        vec![range_start, range_end]
    }
}
#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test() {
        let t = Solution::smallest_range(vec![vec![10], vec![11]]);
        assert_eq!(t, vec![10, 11]);
        //[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
        let t = Solution::smallest_range(vec![
            vec![4, 10, 15, 24, 26],
            vec![0, 9, 12, 20],
            vec![5, 18, 22, 30],
        ]);
        assert_eq!(t, vec![20, 24]);
    }
}