5.10 如何调度考生的座位

5.10.1 问题描述

在考场里，一排有 N 个座位，分别编号为 0, 1, 2, …, N-1 。

当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)

返回 ExamRoom(int N) 类，它有两个公开的函数：其中，函数 ExamRoom.seat() 会返回一个 int （整型数据），代表学生坐的位置；函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。每次调用 ExamRoom.leave§ 时都保证有学生坐在座位 p 上。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/exam-room
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public class ExamRoom {
    //构造函数,传入座位的总数N
    public ExamRoom(int n) {

    }
    //来了一名考生,返回你给它分配的作为
    public int seat() {
        
    }
    //坐在p位置的考生离开了
    public void leave(int p) {

    }
}

• 假设有一个考场，考场一排一共N个座位，索引分别是[0...N-1]，考生会陆续进入考场考生，并且可能在任何时候离开考场，安排座位时满足:每当一个学生进入时，你需要最大化地和最近其他人的距离，如果有多个这样的座位，安排到他的索引最小的那个座位

样例分析:

比如考场有5个座位，索引分别是[0,1,2,3,4]

第一名考生进入时，调用seat(),坐在任何都行，但是要给他安排索引最小的位置，也就是返回数字0

第二名考生进入时，再调用seat(),要和旁边的人距离最远，和0最远的是4

第三名考试进入时，再调用seat(),要和旁边的人距离最远，取得2

如果再进一名学生，可以坐在座位1或者3，取较小的索引1

如果将每两个相邻的考生看作是线段的两个端点，新安排的考生就是找最长的线段，然后让考生在中间在中间把这个线段给二分，中间就是给他分配的座位，leave§其实就是移出端点p，使得相邻两个线段合并为1个

思维点:

[1] 为啥是最长的线段？因为题目要求了距离要和其他考生最远，那么当且仅当在最长的线段上取点的时候才有可能取到最长的点

[2] 为啥是中间? 同样是因为要求与其他考生最远，如果偏左，那么就和左边那个同学近，偏右同理，因此二分取中间点是符合条件的最优解

5.10.2 思路分析

• 首先需要把坐在教室里的学生抽象成线段，可以简单让一个大小为2的数组存储线段的两个端点索引，把它看作为一条线段，另外需要我们找到最长的线段，还需要去除线段，增加线段

**但凡在动态过程中取最值的要求，肯定要使用有序的数据结构，常用的数据结构就是二叉堆和平衡二叉搜索树。**二叉堆实现的优先级队列取最值的时间复杂度是O(logN)，但是只能删除最大值。平衡二叉树也可以取最值，也可以修改、删除任意一个值，而且时间复杂度都是O(logN)

综上所述，二叉堆不能够满足leave操作，应该要使用平衡二叉树，所以这里会用到java的一种数据结构TreeSet，这是一种有序的数据结构，底层由红黑数(一种平衡二叉树)维护其有序性

哈希集合/映射底层是由哈希函数和数组实现的，特性是遍历无固定的顺序，但是操作效率高，时间复杂度为O(1)

集合/映射还可以依赖其他底层的数据结构，常见的就是红黑树，特性是自动维护其中的元素，操作效率是O(logN)这种一般称为"有序集合/映射"

本题中将使用的TreeSet就是一个有序集合，目的就是为了保持线段长度的有序性，快速查找最大线段，快速删除和插入

5.10.3 简化问题

先暂时抛开最小索引的要求，先实现最关键的需求。与之前的那道戳气球类似，我们这里要使用到一个技巧: 虚拟线段，因为题目的base-case是:当没有线段端点存在的时候，第一个线段端点自动放到0，第二个线段端点自动放到n-1的位置上，这种base-case并不是一劳永逸的，因为考生随时可能离开座位，然后回归到base-case，我们希望能够找到一种处理方法，使得base-case也能归到基础问题的处理中

    //将端点p映射到以p为左端点的线段
    private Map<Integer, int[]> startMap;
    //将端点p映射到以p为右端点的线段
    private Map<Integer, int[]> endMap;
    //根据线段大小长度从小到大存放所有的线段
    private TreeSet<int[]> pq;
    private int n;

    //构造函数,传入座位的总数N
    public ExamRoom(int n) {
        this.n = n;
        startMap = new HashMap<>();
        endMap = new HashMap<>();
        pq = new TreeSet<>((a,b)->{
           //算出两个线段的长度
           int distA =  distance(a);
           int distB =  distance(b);
           //长度更长的更大,排后面
            if(distA == distB){
                return b[0] - a[0];
            }
            return distA-distB;
        });
        //在有序集合中存放一个虚拟线段
        this.addInterval(new int[]{-1,this.n});
    }
    //来了一名考生,返回你给它分配的座位
    public int seat() {
        //从有序集合中拿出最长的线段
        int[] longest = pq.last();
        int x  = longest[0];
        int y  = longest[1];
        int seat;
        if(x == -1){
            //情况一:最左边没人的话肯定坐最左边
            seat = 0;
        }else if( y == this.n){
            //情况二:最右边没人,则分配右边的座位
            seat  = this.n-1;
        }else{
            //不是边界的话就坐到中间去
            seat = x + (y-x)/2;
        }
        //新建了端点后,要维护一条新的线段
        int[] left = new int[]{x,seat};
        int[] right = new int[]{seat,y};
        removeInterval(longest);
        addInterval(left);
        addInterval(right);
        return seat;
    }
    //坐在p位置的考生离开了
    public void leave(int p) {
        //将p左右的线段给找出来
        int[] right = startMap.get(p);
        int[] left = endMap.get(p);
        //将两条线段给合并为一条线段
        int[] merged = new int[]{left[0],right[1]};
        //删除旧线段,插入新线段
        removeInterval(left);
        removeInterval(right);
        addInterval(merged);
    }
    //去除线段
    private void removeInterval(int[] intv){
        pq.remove(intv);
        startMap.remove(intv[0]);
        endMap.remove(intv[1]);
    }

    //增加线段
    private void addInterval(int[] intv){
        pq.add(intv);
        startMap.put(intv[0],intv);
        endMap.put(intv[1],intv);
    }

    //计算线段的长度
    private int distance(int[] intv){
        int x = intv[0];
        int y = intv[1];
        if(x == -1){
            return y;
        }
        if(y == this.n){
            return this.n-(x+1);
        }
        //中点和端点之间的长度
        return (y-x)/2;
    }

5.10.4 完善解法

上述的解法将最关键的，最核心的思路已经解决了，接下来我们要解决是最小索引的问题

• 首先明确，遇到这种题目要求，解决方式就是修改有序数据结构的排序方式，我们希望取到的last，其start是比较小的。于是修改

        pq = new TreeSet<>((a,b)->{
           //算出两个线段的长度
           int distA =  distance(a);
           int distB = distance(b);
           //长度更长的更大,排后面
            if(distA == distB){
                return b[0] - a[0];
            }
            return distA-distB;
        });

• 除此之外，还要改变distance函数，不能让它简单地计算一条线段两个端点间的长度，而是让它计算该线段重点和端点之间的长度

    //计算线段的长度
    private int distance(int[] intv){
        int x = intv[0];
        int y = intv[1];
        if(x == -1){
            return y;
        }
        if(y == this.n){
            return this.n-(x+1);
        }
        //中点和端点之间的长度
        return (y-x)/2;
    }