2022-05-10在字节跳动，大家都使用飞书的日历功能进行会议室的预订，遇到会议高峰时期， 会议室就可能不够用，现在请你实现算法，判断预订会议时是否有空的会议室可用。 为简化问题，这里忽略会议

2022-05-10：在字节跳动，大家都使用飞书的日历功能进行会议室的预订，遇到会议高峰时期，
会议室就可能不够用，现在请你实现一个算法，判断预订会议时是否有空的会议室可用。
为简化问题，这里忽略会议室的大小，认为所有的会议室都是等价的，
只要空闲就可以容纳任意的会议，并且：

1. 所有的会议预订都是当日预订当日的时段；
2. 会议时段是一个左闭右开的时间区间，精确到分钟；
3. 每个会议室刚开始都是空闲状态，同一时间一个会议室只能进行一场会议；
4. 会议一旦预订成功就会按时进行。
   比如上午11点到中午12点的会议即[660, 720)，
   给定一个会议室总数m，
   一个预定事件由[a,b,c]代表 :
   a代表预定动作的发生时间，早来早得; b代表会议的召开时间; c代表会议的结束时间，
   给定一个n*3的二维数组，即可表示所有预定事件。
   返回一个长度为n的boolean类型的数组，表示每一个预定时间是否成功。
   来自字节飞书团队。

答案2022-05-10：

线段树。

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

use rand::Rng;

fn main() {
    let mut meetings: Vec<Vec<isize>> = vec![
        vec![6, 100, 200],
        vec![4, 110, 300],
        vec![7, 201, 300],
        vec![9, 199, 320],
    ];
    let answer = reserve_meetings(2, &mut meetings);
    println!("answer = {:?}", answer);

    // 测试线段树的对数器
    let mut rng = rand::thread_rng();
    let nn: isize = 50;
    let vv: isize = 10;
    let test_times1: isize = 1000;
    let test_times2: isize = 1000;
    println!("测试线段树开始");
    for _i in 0..test_times1 {
        let n: isize = rng.gen_range(0, nn)   1;
        let mut st = SegmentTree::new(n);
        let mut right = Right::new(n);
        for _j in 0..test_times2 {
            let a: isize = rng.gen_range(0, n)   1;
            let b: isize = rng.gen_range(0, n)   1;
            let ll: isize = get_min(a, b);
            let rr: isize = get_max(a, b);
            if rng.gen_range(0.0, 1.0) < 0.5 {
                let cc: isize = rng.gen_range(0, vv);
                st.add(ll, rr, cc);
                right.add(ll, rr, cc);
            } else {
                if st.query_max(ll, rr) != right.query_max(ll, rr) {
                    println!("出错了!");
                }
            }
        }
    }
    println!("测试线段树结束");
}

fn reserve_meetings(m: isize, meetings: &mut Vec<Vec<isize>>) -> Vec<bool> {
    // 会议的总场次
    let n: isize = meetings.len() as isize;
    // 开头时间，结尾时间
    let mut ranks: Vec<isize> = vec![];
    for _i in 0..n << 1 {
        ranks.push(0);
    }
    for i in 0..n {
        ranks[i as usize] = meetings[i as usize][1];
        ranks[(i   n) as usize] = meetings[i as usize][2] - 1;
    }
    ranks.sort_unstable();
    // 0 : [6, 100, 200]
    // 1 : [4, 30,  300]
    // 30,1  100,2  200,3  300,4
    // [0,6,2,3]
    // [1,4,1,4]
    //
    // 0 T/F ,  1,  T/  2,

    // [1,4,1,4]   [0,6,2,3]  ....
    let mut re_meetings: Vec<Vec<isize>> = vec![];
    for i in 0..n {
        re_meetings.push(vec![]);
        for _j in 0..4 {
            re_meetings[i as usize].push(0);
        }
    }
    let mut max: isize = 0;
    for i in 0..n {
        re_meetings[i as usize][0] = i;
        re_meetings[i as usize][1] = meetings[i as usize][0];
        re_meetings[i as usize][2] = rank(&mut ranks, meetings[i as usize][1]);
        re_meetings[i as usize][3] = rank(&mut ranks, meetings[i as usize][2] - 1);
        max = get_max(max, re_meetings[i as usize][3]);
    }
    let mut st: SegmentTree = SegmentTree::new(max);
    re_meetings.sort_by(|a, b| a[1].cmp(&b[1]));
    let mut ans: Vec<bool> = vec![];
    for _i in 0..n {
        ans.push(false);
    }
    for i in 0..re_meetings.len() {
        if st.query_max(re_meetings[i as usize][2], re_meetings[i as usize][3]) < m {
            ans[re_meetings[i as usize][0] as usize] = true;
            st.add(re_meetings[i as usize][2], re_meetings[i as usize][3], 1);
        }
    }
    return ans;
}

// 返回>=num, 最左位置
fn rank(sorted: &mut Vec<isize>, num: isize) -> isize {
    let mut l: isize = 0;
    let mut r: isize = sorted.len() as isize - 1;
    let mut m: isize;
    let mut ans: isize = 0;
    while l <= r {
        m = (l   r) / 2;
        if sorted[m as usize] >= num {
            ans = m;
            r = m - 1;
        } else {
            l = m   1;
        }
    }
    return ans   1;
}

pub struct SegmentTree {
    pub n: isize,
    pub max: Vec<isize>,
    pub lazy: Vec<isize>,
}

fn get_max(a: isize, b: isize) -> isize {
    if a > b {
        a
    } else {
        b
    }
}

fn get_min(a: isize, b: isize) -> isize {
    if a < b {
        a
    } else {
        b
    }
}

impl SegmentTree {
    pub fn new(max_size: isize) -> SegmentTree {
        let mut max: Vec<isize> = vec![];
        let mut lazy: Vec<isize> = vec![];
        for _i in 0..max_size << 2 {
            max.push(0);
            lazy.push(0);
        }
        SegmentTree {
            n: max_size,
            max: max,
            lazy: lazy,
        }
    }

    pub fn push_up(&mut self, rt: isize) {
        self.max[rt as usize] = get_max(
            self.max[(rt << 1) as usize],
            self.max[(rt << 1 | 1) as usize],
        );
    }

    pub fn push_down(&mut self, rt: isize, _ln: isize, _rn: isize) {
        if self.lazy[rt as usize] != 0 {
            self.lazy[(rt << 1) as usize]  = self.lazy[rt as usize];
            self.max[(rt << 1) as usize]  = self.lazy[rt as usize];
            self.lazy[(rt << 1 | 1) as usize]  = self.lazy[rt as usize];
            self.max[(rt << 1 | 1) as usize]  = self.lazy[rt as usize];
            self.lazy[rt as usize] = 0;
        }
    }

    pub fn add(&mut self, ll: isize, rr: isize, cc: isize) {
        self.add2(ll, rr, cc, 1, self.n, 1);
    }

    pub fn add2(&mut self, ll: isize, rr: isize, cc: isize, l: isize, r: isize, rt: isize) {
        if ll <= l && r <= rr {
            self.max[rt as usize]  = cc;
            self.lazy[rt as usize]  = cc;
            return;
        }
        let mid: isize = (l   r) >> 1;
        self.push_down(rt, mid - l   1, r - mid);
        if ll <= mid {
            self.add2(ll, rr, cc, l, mid, rt << 1);
        }
        if rr > mid {
            self.add2(ll, rr, cc, mid   1, r, rt << 1 | 1);
        }
        self.push_up(rt);
    }

    pub fn query_max(&mut self, ll: isize, rr: isize) -> isize {
        return self.query_max2(ll, rr, 1, self.n, 1);
    }

    pub fn query_max2(&mut self, ll: isize, rr: isize, l: isize, r: isize, rt: isize) -> isize {
        if ll <= l && r <= rr {
            return self.max[rt as usize];
        }
        let mid: isize = (l   r) >> 1;
        self.push_down(rt, mid - l   1, r - mid);
        let mut ans: isize = 0;
        if ll <= mid {
            ans = get_max(ans, self.query_max2(ll, rr, l, mid, rt << 1));
        }
        if rr > mid {
            ans = get_max(ans, self.query_max2(ll, rr, mid   1, r, rt << 1 | 1));
        }
        return ans;
    }
}

// 为了测试线段树
pub struct Right {
    pub arr: Vec<isize>,
}

impl Right {
    pub fn new(max_size: isize) -> Right {
        let mut arr: Vec<isize> = vec![];
        for _i in 0..max_size   1 {
            arr.push(0);
        }
        Right { arr: arr }
    }

    pub fn add(&mut self, ll: isize, rr: isize, cc: isize) {
        for i in ll..=rr {
            self.arr[i as usize]  = cc;
        }
    }

    pub fn query_max(&mut self, ll: isize, rr: isize) -> isize {
        let mut ans: isize = 0;
        for i in ll..=rr {
            ans = get_max(ans, self.arr[i as usize]);
        }
        return ans;
    }
}

执行结果如下：

左神java代码

这篇好文章是转载于：学新通技术网