impl Solution {
    pub fn car_fleet(target: i32, position: Vec<i32>, speed: Vec<i32>) -> i32 {
        let n = position.len();
        if n == 0 || n == 1 {
            return n as i32;
        }
        let mut src = vec![(0, 0.); n];
        for i in 0..n {
            src[i].0 = position[i];
            src[i].1 = (target - position[i]) as f64 / speed[i] as f64;
        }

        src.sort_by_key(|x| x.0);
        let mut ans = 0;
        for i in (1..n).rev() {
            if src[i].1 < src[i - 1].1 {
                ans += 1; continue;
            }
            src[i - 1] = src[i];
        }
        return ans + 1;
    }
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    fn get_max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if let Some(node) = root {
            return std::cmp::max(Self::get_max_depth(RefCell::borrow(&node).left.clone()),
                                 Self::get_max_depth(RefCell::borrow(&node).right.clone())) + 1;
        } else {
            return 0;
        }
    }

    pub fn subtree_with_all_deepest(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(node) = root {
            let diff = Self::get_max_depth(RefCell::borrow(&node).left.clone()) -
                Self::get_max_depth(RefCell::borrow(&node).right.clone());
            if diff == 0 {
                return Some(node);
            } else if diff > 0 {
                return Self::subtree_with_all_deepest(RefCell::borrow(&node).left.clone());
            } else {
                return Self::subtree_with_all_deepest(RefCell::borrow(&node).right.clone());
            }
        } else {
            return root;
        }
    }
}

use std::collections::BinaryHeap;

impl Solution {
    pub fn min_refuel_stops(target: i32, start_fuel: i32, stations: Vec<Vec<i32>>) -> i32 {
        let (mut cur, mut stops, mut i) = (start_fuel, 0, 0);
        let mut q = BinaryHeap::new();
        loop {
            if cur >= target {
                return stops;
            }
            while i < stations.len() && stations[i][0] <= cur {
                q.push(stations[i][1]);
                i += 1;
            }
            if q.is_empty() {
                break;
            }
            cur += q.pop().unwrap();
            stops += 1;
        }

        return -1;
    }
}