2022-05-21：给定一个数组arr，长度为n， 表示n个服务员，每个人服务一个人的时间。 给定一个正数m，表示有m个人等位。 如果你是刚来的人，请问你需要等多久？ 假设：m远远大于n，比如n<=1000, m <= 10的9次方，该怎么做？ 来自谷歌。

答案2022-05-21：

方法一：小根堆。时间复杂度：O(mlogN)。 方法二：二分法。时间复杂度：O(Nlogm)。

代码用rust编写。代码如下：

use rand::Rng;

fn main() {
    let len: i32 = 50;
    let value: i32 = 30;
    let m_max: i32 = 3000;
    let test_time: i32 = 500;
    println!("测试开始");
    for _i in 0..test_time {
        let n: i32 = rand::thread_rng().gen_range(0, len) + 1;
        let mut arr = random_array(n, value);
        let m = rand::thread_rng().gen_range(0, m_max);
        let ans1 = min_waiting_time1(&mut arr, m);
        let ans2 = min_waiting_time2(&mut arr, m);
        if ans1 != ans2 {
            println!("出错了!");
            for num in arr.iter() {
                println!("{} ", num);
            }
            println!("");
            println!("m = {}", m);
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            break;
        }
    }
    println!("测试结束");
}

fn min_waiting_time1(arr: &mut Vec<i32>, m: i32) -> i32 {
    if arr.len() == 0 {
        return -1;
    }
    let mut heap: Vec<Vec<i32>> = vec![];
    let n = arr.len() as i32;
    for i in 0..n {
        heap.push(vec![0, arr[i as usize]]);
    }
    for _i in 0..m {
        heap.sort_by(|x, y| y[0].cmp(&x[0]));
        let hi = heap.len() - 1;
        heap[hi][0] += heap[hi][1];
    }
    heap.sort_by(|x, y| y[0].cmp(&x[0]));
    return heap[heap.len() - 1][0];
}

fn min_waiting_time2(arr: &mut Vec<i32>, m: i32) -> i32 {
    if arr.len() == 0 {
        return -1;
    }
    let mut best: i32 = 2147483647;
    for num in arr.iter() {
        best = if best < *num { best } else { *num };
    }
    let mut left: i32 = 0;
    let mut right: i32 = best * m;
    let mut mid: i32 = 0;
    let mut near: i32 = 0;
    while left <= right {
        mid = (left + right) / 2;
        let mut cover: i32 = 0;
        for num in arr.iter() {
            cover += (mid / *num) + 1;
        }
        if cover >= m + 1 {
            near = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return near;
}

// 为了测试
fn random_array(n: i32, v: i32) -> Vec<i32> {
    let mut arr: Vec<i32> = vec![];
    for _i in 0..n {
        arr.push(rand::thread_rng().gen_range(0, v) + 1);
    }
    return arr;
}

执行结果如下：

在这里插入图片描述

左神java代码