2022-06-09：每个会议给定开始和结束时间， 后面的会议如果跟前面的会议有任何冲突，完全取消冲突的、之前的会议，安排当前的。 给定一个会议数组，返回安排的会议列表。 来自通维数码。
答案2022-06-09：
彻底的流程模拟。线段树。
代码用rust编写。代码如下：
use rand::Rng;
fn main() {
let n: i32 = 100;
let t: i32 = 5000;
let test_time: i32 = 20000;
println!("测试开始");
for _ in 0..test_time {
let len: i32 = rand::thread_rng().gen_range(0, n) + 1;
let mut meetings1 = random_meeting(len, t);
let mut meetings2 = copy_meetings(&mut meetings1);
let mut ans1 = arrange1(&mut meetings1);
let mut ans2 = arrange2(&mut meetings2);
if !equal(&mut ans1, &mut ans2) {
println!("出错了!");
println!("ans1 = {:?}", ans1);
println!("ans2 = {:?}", ans2);
println!("===============");
}
}
println!("测试结束");
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}
// 比较暴力的解
// 为了对数器来验证
fn arrange1(meetings: &mut Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut max = 0;
for meeting in meetings.iter_mut() {
max = get_max(max, meeting[1]);
}
let mut occupy: Vec<bool> = vec![];
for _ in 0..max + 1 {
occupy.push(false);
}
let mut ans: Vec<Vec<i32>> = vec![];
let mut i = meetings.len() as i32 - 1;
while i >= 0 {
let cur = &meetings[i as usize];
let mut add = true;
let mut j = cur[0];
while j < cur[1] {
if occupy[j as usize] {
add = false;
break;
}
j += 1;
}
if add {
ans.push(cur.clone());
}
let mut j = cur[0];
while j < cur[1] {
occupy[j as usize] = true;
j += 1;
}
i -= 1;
}
return ans;
}
// 最优解
// 会议有N个，时间复杂度O(N*logN)
fn arrange2(meetings: &mut Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let n = meetings.len() as i32;
// n << 1 -> n*2
let mut rank0: Vec<i32> = vec![];
for _ in 0..n << 1 {
rank0.push(0);
}
for i in 0..meetings.len() as i32 {
rank0[i as usize] = meetings[i as usize][0]; // 会议开头点
rank0[(i + n) as usize] = meetings[i as usize][1] - 1; // 会议的结束点
}
//Arrays.sort(rank);
rank0.sort();
// n*2
//SegmentTree st = new SegmentTree(n << 1);
let mut st: SegmentTree = SegmentTree::new(n << 1);
// 哪些会议安排了，放入到ans里去！
//ArrayList<int[]> ans = new ArrayList<>();
let mut ans: Vec<Vec<i32>> = vec![];
// 从右往左遍历，意味着，后出现的会议，先看看能不能安排
let mut i = meetings.len() as i32 - 1;
while i >= 0 {
// cur 当前会议
let cur = &meetings[i as usize];
// cur[0] = 17万 -> 6
let from = rank(&mut rank0, cur[0]);
// cur[1] = 90 -> 89 -> 2
let to = rank(&mut rank0, cur[1] - 1);
if st.sum(from, to) == 0 {
ans.push(cur.clone());
}
st.add(from, to, 1);
i -= 1;
}
return ans;
}
fn rank(rank: &mut Vec<i32>, num: i32) -> i32 {
let mut l = 0;
let mut r = rank.len() as i32 - 1;
let mut m = 0;
let mut ans = 0;
while l <= r {
m = (l + r) / 2;
if rank[m as usize] >= num {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans + 1;
}
pub struct SegmentTree {
pub n: i32,
pub sum: Vec<i32>,
pub lazy: Vec<i32>,
}
impl SegmentTree {
pub fn new(size: i32) -> Self {
let mut sum: Vec<i32> = vec![];
let mut lazy: Vec<i32> = vec![];
for _ in 0..(size + 1) << 2 {
sum.push(0);
lazy.push(0);
}
Self {
n: size + 1,
sum,
lazy,
}
}
fn push_up(&mut self, rt: i32) {
self.sum[rt as usize] = self.sum[(rt << 1) as usize] + self.sum[(rt << 1 | 1) as usize];
}
fn push_down(&mut self, rt: i32, ln: i32, rn: i32) {
if self.lazy[rt as usize] != 0 {
self.lazy[(rt << 1) as usize] += self.lazy[rt as usize];
self.sum[(rt << 1) as usize] += self.lazy[rt as usize] * ln;
self.lazy[(rt << 1 | 1) as usize] += self.lazy[rt as usize];
self.sum[(rt << 1 | 1) as usize] += self.lazy[rt as usize] * rn;
self.lazy[rt as usize] = 0;
}
}
pub fn add(&mut self, L: i32, R: i32, C: i32) {
self.add0(L, R, C, 1, self.n, 1);
}
fn add0(&mut self, L: i32, R: i32, C: i32, l: i32, r: i32, rt: i32) {
if L <= l && r <= R {
self.sum[rt as usize] += C * (r - l + 1);
self.lazy[rt as usize] += C;
return;
}
let mid = (l + r) >> 1;
self.push_down(rt, mid - l + 1, r - mid);
if L <= mid {
self.add0(L, R, C, l, mid, rt << 1);
}
if R > mid {
self.add0(L, R, C, mid + 1, r, rt << 1 | 1);
}
self.push_up(rt);
}
pub fn sum(&mut self, L: i32, R: i32) -> i32 {
return self.query(L, R, 1, self.n, 1);
}
fn query(&mut self, L: i32, R: i32, l: i32, r: i32, rt: i32) -> i32 {
if L <= l && r <= R {
return self.sum[rt as usize];
}
let mid = (l + r) >> 1;
self.push_down(rt, mid - l + 1, r - mid);
let mut ans = 0;
if L <= mid {
ans += self.query(L, R, l, mid, rt << 1);
}
if R > mid {
ans += self.query(L, R, mid + 1, r, rt << 1 | 1);
}
return ans;
}
}
// 为了测试
fn random_meeting(len: i32, time: i32) -> Vec<Vec<i32>> {
let mut meetings: Vec<Vec<i32>> = vec![];
for i in 0..len {
meetings.push(vec![]);
for _ in 0..2 {
meetings[i as usize].push(0);
}
}
for i in 0..len {
let mut a = rand::thread_rng().gen_range(0, time + 1);
let mut b = rand::thread_rng().gen_range(0, time + 1);
if a == b {
b += 1;
}
meetings[i as usize][0] = get_min(a, b);
meetings[i as usize][1] = get_max(a, b);
}
return meetings;
}
// 为了测试
fn copy_meetings(meetings: &mut Vec<Vec<i32>>) -> Vec<Vec<i32>> {
return meetings.clone();
// let mut len = meetings.len() as i32;
// let mut ans:Vec<Vec<i32>>=vec![];
// for i in 0..len {
// // ans[i][0] = meetings[i][0];
// // ans[i][1] = meetings[i][1];
// }
// return ans;
}
// 为了测试
fn equal(arr1: &mut Vec<Vec<i32>>, arr2: &mut Vec<Vec<i32>>) -> bool {
if arr1.len() != arr2.len() {
return false;
}
for i in 0..arr1.len() {
if arr1[i][0] != arr2[i][0] || arr1[i][1] != arr2[i][1] {
return false;
}
}
return true;
}
执行结果如下：
京公网安备 11010502036488号