leetcode-rust/src/leetcode/problem/min_eating_speed.rs at main · martwz/leetcode-rust · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// 875. Koko Eating Bananas, Medium
// https://leetcode.com/problems/koko-eating-bananas/
impl Solution {
    pub fn min_eating_speed(piles: Vec<i32>, h: i32) -> i32 {
        if piles.is_empty() {
            return 0;
        }

        let [mut lo, mut hi] = [0, i32::max_value()];

        fn can_eat(piles: &Vec<i32>, h: i32, k: i32) -> bool {
            let mut hours = 0;
            piles.iter().for_each(|p| {
                hours += f64::ceil(*p as f64 / k as f64) as i32;
            });
            hours <= h
        }

        while hi - lo > 1 {
            let mid = lo + (hi - lo) / 2;
            if can_eat(&piles, h, mid) {
                hi = mid;
            } else {
                lo = mid;
            }
        }

        hi
    }
}

struct Solution {}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_min_eating_speed() {
        assert_eq!(Solution::min_eating_speed(vec![3, 6, 7, 11], 8), 4);
    }

    #[test]
    fn test_min_eating_speed2() {
        assert_eq!(Solution::min_eating_speed(vec![3], 3), 1);
    }

    #[test]
    fn test_min_eating_speed3() {
        assert_eq!(Solution::min_eating_speed(vec![], 3), 0);
    }

    #[test]
    fn test_min_eating_speed4() {
        assert_eq!(
            Solution::min_eating_speed(
                vec![
                    332484035, 524908576, 855865114, 632922376, 222257295, 690155293, 112677673, 679580077, 337406589, 290818316, 877337160, 901728858, 679284947, 688210097,
                    692137887, 718203285, 629455728, 941802184
                ],
                823855818
            ),
            14
        );
    }
}