在字节跳动，大家都使用飞书的日历功能进行会议室的预订，遇到会议高峰时期，
会议室就可能不够用，现在请你实现一个算法，判断预订会议时是否有空的会议室可用。
为简化问题，这里忽略会议室的大小，认为所有的会议室都是等价的，
只要空闲就可以容纳任意的会议，并且：
- 所有的会议预订都是当日预订当日的时段；
- 会议时段是一个左闭右开的时间区间，精确到分钟；
- 每个会议室刚开始都是空闲状态，同一时间一个会议室只能进行一场会议；
- 会议一旦预订成功就会按时进行。
比如上午11点到中午12点的会议即[660, 720)，
给定一个会议室总数m，
一个预定事件由[a,b,c]代表 :
a代表预定动作的发生时间，早来早得; b代表会议的召开时间; c代表会议的结束时间，
给定一个n*3的二维数组，即可表示所有预定事件。
返回一个长度为n的boolean类型的数组，表示每一个预定时间是否成功。
线段树。
代码用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;
}
}执行结果如下：
