855. 考场就座（高频题）

855. 考场就座

• 题目
• 解题思路
• 代码

题目

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

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

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

解题思路

见书P389

代码

    class ExamRoom {
        private Map<Integer, int[]> startMap;
        private Map<Integer, int[]> endMap;
        private TreeSet<int[]> pq;
        private int N;

        /**
         * 构造函数，传入座位总数N
         *
         * @param N
         */
        public ExamRoom(int N) {
            this.N = N;
            startMap = new HashMap<>();
            endMap = new HashMap<>();
            pq = new TreeSet<int[]>((a, b) -> {
                //算出两个线段的长度
                int disA = distance(a);
                int disB = distance(b);
                //如果长度相同就比较索引
                if (disA == disB) {
                    return b[0] - a[0];
                }
                return disA - disB;
            });
            //在有序集合中先放一个虚拟线段
            addInterval(new int[]{-1, N});
        }

        /**
         * 来一名考生，返回你给他分配的座位
         *
         * @return
         */
        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 == N) {
                seat = N - 1;
            } else {
                seat = (y - x) / 2 + x;
            }

            // 将最长的线段分成两段
            int[] left = new int[]{x, seat};
            int[] right = new int[]{seat, y};

            removeInterval(longest);
            addInterval(left);
            addInterval(right);

            return seat;
        }

        /**
         * 坐在p位置的考生离开了
         *
         * @param 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);
        }


        /*一些需要用到的API*/

        //去除线段
        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 == N) {
                return N - x - 1;
            }

            //中点和端点之间的长度
            return (y - x) / 2;
        }
    }

/**
 * Your ExamRoom object will be instantiated and called as such:
 * ExamRoom obj = new ExamRoom(N);
 * int param_1 = obj.seat();
 * obj.leave(p);
 */