mzoe666888

V1

2022/06/09阅读:22主题:兰青

内卷大厂系列《线段树-会议室问题》

《线段树/树状数组》,您将学到线段树能解决什么问题以及运用场景,如何快速实现整体批量更新修改、批量查询,线段树是不错的选择,来自字节飞书团队算法面试题

一、题目

来自字节飞书团队算法面试题

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

  1. 所有的会议预订都是当日预订当日的时段
  2. 会议时段是一个左闭右开的时间区间,精确到分钟
  3. 每个会议室刚开始都是空闲状态,同一时间一个会议室只能进行一场会议
  4. 会议一旦预订成功就会按时进行

比如上午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