
mzoe666888
V1
2022/06/09阅读:22主题:兰青
内卷大厂系列《线段树-会议室问题》
《线段树/树状数组》,您将学到线段树能解决什么问题以及运用场景,如何快速实现整体批量更新修改、批量查询,线段树是不错的选择,来自字节飞书团队算法面试题。
一、题目
来自字节飞书团队算法面试题
在字节跳动,大家都使用飞书的日历功能进行会议室的预订,遇到会议高峰时期,会议室就可能不够用,现在请你实现一个算法,判断预订会议时是否有空的会议室可用。为简化问题,这里忽略会议室的大小,认为所有的会议室都是等价的,只要空闲就可以容纳任意的会议,并且:
-
所有的会议预订都是当日预订当日的时段 -
会议时段是一个左闭右开的时间区间,精确到分钟 -
每个会议室刚开始都是空闲状态,同一时间一个会议室只能进行一场会议 -
会议一旦预订成功就会按时进行
比如上午11点到中午12点的会议即[660, 720)
给定一个会议室总数m,一个预定事件由[a,b,c]代表 : a代表预定动作的发生时间,早来早得; b代表会议的召开时间; c代表会议的结束时间。
给定一个n*3
的二维数组,即可表示所有预定事件,返回一个长度为n的boolean类型的数组,表示每一个预定时间是否成功。
二、分析
会议室预订相比大家都用过,一个事件的发生包括几个属性,何时预订的,也就是预订时间,预订的会议室的开始时间和结束时间,也就是上述用预订事件[a,b,c]代表的含义,a代表预订动作发生的时间,b代表会议的开始时间,c代表会议的结束时间。同一时间段只能进行一场会议,如果会议室很多,那么同一时间段可以进行多场会议,现实开会就是这样的场景,只不过是在不同的会议室而已。题目给定了总共有m间会议室。
这道题的本质就是利用线段树来实现快速更新和快速查找,如果不用线段树来做,也可以,就是执行效率的问题,利用线段树能做到时间复杂度为O(logN),不用线段树通过遍历的方式来做,时间复杂度为O(N)
其次就是线段树的空间离散化问题,需要处理,开辟多大的空间,避免浪费。
三、实现
public static boolean[] reserveMeetings(int m, int[][] meetings) {
// 会议的总场次
int n = meetings.length;
// 开头时间,结尾时间
int[] ranks = new int[n << 1];
for (int i = 0; i < n; i++) {
ranks[i] = meetings[i][1];
ranks[i + n] = meetings[i][2] - 1;
}
Arrays.sort(ranks);
// 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] ....
int[][] reMeetings = new int[n][4];
int max = 0;
for (int i = 0; i < n; i++) {
reMeetings[i][0] = i;
reMeetings[i][1] = meetings[i][0];
reMeetings[i][2] = rank(ranks, meetings[i][1]);
reMeetings[i][3] = rank(ranks, meetings[i][2] - 1);
max = Math.max(max, reMeetings[i][3]);
}
SegmentTree st = new SegmentTree(max);
Arrays.sort(reMeetings, (a, b) -> a[1] - b[1]);
boolean[] ans = new boolean[n];
for (int[] meeting : reMeetings) {
if (st.queryMax(meeting[2], meeting[3]) < m) {
ans[meeting[0]] = true;
st.add(meeting[2], meeting[3], 1);
}
}
return ans;
}
// 返回>=num, 最左位置
public static int rank(int[] sorted, int num) {
int l = 0;
int r = sorted.length - 1;
int m = 0;
int ans = 0;
while (l <= r) {
m = (l + r) / 2;
if (sorted[m] >= num) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans + 1;
}
public static class SegmentTree {
private int n;
private int[] max;
private int[] lazy;
public SegmentTree(int maxSize) {
n = maxSize;
max = new int[n << 2];
lazy = new int[n << 2];
}
private void pushUp(int rt) {
max[rt] = Math.max(max[rt << 1], max[rt << 1 | 1]);
}
private void pushDown(int rt, int ln, int rn) {
if (lazy[rt] != 0) {
lazy[rt << 1] += lazy[rt];
max[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
max[rt << 1 | 1] += lazy[rt];
lazy[rt] = 0;
}
}
public void add(int L, int R, int C) {
add(L, R, C, 1, n, 1);
}
private void add(int L, int R, int C, int l, int r, int rt) {
if (L <= l && r <= R) {
max[rt] += C;
lazy[rt] += C;
return;
}
int mid = (l + r) >> 1;
pushDown(rt, mid - l + 1, r - mid);
if (L <= mid) {
add(L, R, C, l, mid, rt << 1);
}
if (R > mid) {
add(L, R, C, mid + 1, r, rt << 1 | 1);
}
pushUp(rt);
}
public int queryMax(int L, int R) {
return queryMax(L, R, 1, n, 1);
}
private int queryMax(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
return max[rt];
}
int mid = (l + r) >> 1;
pushDown(rt, mid - l + 1, r - mid);
int ans = 0;
if (L <= mid) {
ans = Math.max(ans, queryMax(L, R, l, mid, rt << 1));
}
if (R > mid) {
ans = Math.max(ans, queryMax(L, R, mid + 1, r, rt << 1 | 1));
}
return ans;
}
}
作者介绍

mzoe666888
V1