考场就座 | 沉起

考场就座(medium)

做题过程

真的不会，想不到啊。

算法概述

本题要求为设计一个类来管理考场座位，使新加入的学生的座位总是远离别人（达到最大距离）。需要使用 优先队列 和 有序集合 来管理座位区间，进而对距离进行计算，还需要使用 延迟删除 同步在删除学生的同时更新队列。

时间复杂度为O(logm)：都是对数据结构（有序集合和优先队列/堆的操作）
空间复杂度为O(m)：一个学生一个区间，加上删除操作，小于等于2*m个数字要保存

JAVA

class ExamRoom {
    int n;
    // 存已经有人坐的位子编号
    TreeSet<Integer> seats;
    // 距离区间
    PriorityQueue<int[]> pq;

    public ExamRoom(int n) {
        this.n=n;
        this.seats=new TreeSet<Integer>();
        this.pq=new PriorityQueue<int[]>((a,b)->{
            // 比较区间长度
            int d1=a[1]-a[0],d2=b[1]-b[0];
            /**
             * 区间距离升序
             * 相等时根据左边界的大小来排，此时为降序（题目要求多个相等则取编号最小）
             * 比较器必须返回一个数才行
             */
            return d1/2<d2/2||(d1/2==d2/2&&a[0]>b[0])?1:-1;
        });
    }
    
    public int seat() {
        // 空的时候直接坐到0位子上
        if(seats.isEmpty()){
            seats.add(0);
            return 0;
        }
        /**
         * 多个座位：最左边的座位以及最右边的座位到右边界的距离（因为会有人走，所以需要动态维护） 
         * 一个座位：座位到左边界和右边界的距离
         */ 
        int left=seats.first(),right=n-1-seats.last();
        while(seats.size()>=2){
            // ‘最大的距离区间
            int[] p=pq.peek();
            // 判断是否该距离区间中的两个座位已被占用，以及两个座位之间没有其他座位
            if(seats.contains(p[0])&&seats.contains(p[1])&&seats.higher(p[0])==p[1]){
                // 计算
                int d=p[1]-p[0];
                // 判断区间中点是否有效，无效则退出循环
                if(d/2<right||d/2<=left) break;
                // 区间中点有效则弹出当前区间（使用当前区间）
                pq.poll();
                // 创建两个新区间加入优先队列
                pq.offer(new int[]{p[0],p[0]+d/2});
                pq.offer(new int[]{p[0]+d/2,p[1]});
                // 告知有序集合新的被占座位
                seats.add(p[0]+d/2);
                // 返回中点编号
                return p[0]+d/2;
            }
            // 没有被占用说明当前区间不作数，找上一个区间
            pq.poll();
        }
        // 一个座位的情况
        // 当离右边界距离更大，选取右边界作为新的座位
        if(right>left){
            pq.offer(new int[]{seats.last(),n-1});
            seats.add(n-1);
            return n-1;
            // 当离左边界距离更大，选取左边界作为新的座位
        }else{
            pq.offer(new int[]{0,seats.first()});
            seats.add(0);
            return 0;
        }
    }
    
    public void leave(int p) {
        // 如果删除的不是最小或者最大的座位
        if(p!=seats.first()&&p!=seats.last()){
            // 延迟删除
            // 找到前驱和后继，形成新的区间
            int prev=seats.lower(p),next=seats.higher(p);
            pq.offer(new int[]{prev,next});
        }
        // 删除
        seats.remove(p);
    }
}

重要实例方法及属性(JAVA)

TreeSet.lower()和TreeSet.higher()：和ceiling以及floor()不同的是，后两者为 非严格 ，前两者是严格。

总结

这道题利用了多个数据结构的特性以及技巧。

有序集合：实时得到 最小值和最大值
优先队列：保存区间元素，使用 灵活的自定义比较器
延迟删除：在找到前驱和后继组成新的区间（i.e., 图论的收缩边）后再删除该节点

好难啊😐