关于算法:如何调度考生的座位

读完本文，你能够去力扣拿下如下题目：

855. 考场就座

———–

这是 LeetCode 第 855 题，乏味且具备肯定技巧性。这种题目并不像动静布局这类算法拼智商，而是看你对罕用数据结构的了解和写代码的程度，集体认为值得器重和学习。

另外说句题外话，很多读者都问，算法框架是如何总结进去的，其实框架反而是缓缓从细节里抠出来的。心愿大家看了咱们的文章之后，最好能抽时间把相干的问题亲自做一做，纸上得来终觉浅，绝知此事要躬行嘛。

先来形容一下题目：假如有一个考场，考场有一排共 N 个座位，索引别离是 [0..N-1]，考生会 陆续 进入考场考试，并且可能在 任何时候 来到考场。

你作为考官，要安顿考生们的座位，满足：每当一个学生进入时，你须要最大化他和最近其他人的间隔；如果有多个这样的座位，安顿到他到索引最小的那个座位。这很符合实际状况对吧，

也就是请你实现上面这样一个类：

class ExamRoom {
    // 构造函数，传入座位总数 N
    public ExamRoom(int N);
    // 来了一名考生，返回你给他调配的座位
    public int seat();
    // 坐在 p 地位的考生来到了
    // 能够认为 p 地位肯定坐有考生
    public void leave(int p);
}

比方说考场有 5 个座位，别离是 [0..4]：

第一名考生进入时（调用 seat()），坐在任何地位都行，然而要给他安顿索引最小的地位，也就是返回地位 0。

第二名学生进入时（再调用 seat()），要和旁边的人间隔最远，也就是返回地位 4。

第三名学生进入时，要和旁边的人间隔最远，应该做到两头，也就是座位 2。

如果再进一名学生，他能够坐在座位 1 或者 3，取较小的索引 1。

以此类推。

方才所说的状况，没有调用 leave 函数，不过读者必定可能发现法则：

如果将每两个相邻的考生看做线段的两端点，新安顿考生就是找最长的线段，而后让该考生在两头把这个线段「二分」，中点就是给他调配的座位。leave(p) 其实就是去除端点 p，使得相邻两个线段合并为一个。

外围思路很简略对吧，所以这个问题实际上切实考查你对数据结构的了解。对于上述这个逻辑，你用什么数据结构来实现呢？

一、思路剖析

根据上述思路，首先须要把坐在教室的学生形象成线段，咱们能够简略的用一个大小为 2 的数组示意。

另外，思路须要咱们找到「最长」的线段，还须要去除线段，减少线段。

凡是遇到在动静过程中取最值的要求，必定要应用有序数据结构，咱们罕用的数据结构就是二叉堆和均衡二叉搜寻树了。二叉堆实现的优先级队列取最值的工夫复杂度是 O(logN)，然而只能删除最大值。均衡二叉树也能够取最值，也能够批改、删除任意一个值，而且工夫复杂度都是 O(logN)。

综上，二叉堆不能满足 leave 操作，应该应用均衡二叉树。所以这里咱们会用到 Java 的一种数据结构 TreeSet，这是一种有序数据结构，底层由红黑树保护有序性。

这里顺便提一下，一说到汇合（Set）或者映射（Map），有的读者可能就想当然的认为是哈希汇合（HashSet）或者哈希表（HashMap），这样了解是有点问题的。

因为哈希汇合 / 映射底层是由哈希函数和数组实现的，个性是遍历无固定程序，然而操作效率高，工夫复杂度为 O(1)。

而汇合 / 映射还能够依赖其余底层数据结构，常见的就是红黑树（一种均衡二叉搜寻树），个性是主动保护其中元素的程序，操作效率是 O(logN)。这种个别称为「有序汇合 / 映射」。

咱们应用的 TreeSet 就是一个有序汇合，目标就是为了放弃线段长度的有序性，疾速查找最大线段，疾速删除和插入。

二、简化问题

首先，如果有多个可选座位，须要抉择索引最小的座位对吧？咱们先简化一下问题，临时不论这个要求，实现上述思路。

这个问题还用到一个罕用的编程技巧，就是应用一个「虚构线段」让算法正确启动，这就和链表相干的算法须要「虚构头结点」一个情理。

// 将端点 p 映射到以 p 为左端点的线段
private Map<Integer, int[]> startMap;
// 将端点 p 映射到以 p 为右端点的线段
private Map<Integer, int[]> endMap;
// 依据线段长度从小到大寄存所有线段
private TreeSet<int[]> pq;
private int 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);
        // 长度更长的更大，排前面
        return distA - distB;
    });
    // 在有序汇合中先放一个虚构线段
    addInterval(new int[] {-1, N});
}

/* 去除一个线段 */
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) {return intv[1] - intv[0] - 1;
}

「虚构线段」其实就是为了将所有座位示意为一个线段：

有了上述铺垫，次要 API seat 和 leave 就能够写了：

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;
}

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);
}

![三种状况]

至此，算法就根本实现了，代码虽多，但思路很简略：找最长的线段，从两头分隔成两段，中点就是 seat() 的返回值；找 p 的左右线段，合并成一个线段，这就是 leave(p) 的逻辑。

三、进阶问题

然而，题目要求多个抉择时抉择索引最小的那个座位，咱们方才疏忽了这个问题。比方上面这种状况会出错：

当初有序汇合里有线段 [0,4] 和 [4,9]，那么最长线段 longest 就是后者，依照 seat 的逻辑，就会宰割 [4,9]，也就是返回座位 6。但正确答案应该是座位 2，因为 2 和 6 都满足最大化相邻考生间隔的条件，二者应该取较小的。

遇到题目的这种要求，解决形式就是批改有序数据结构的排序形式。具体到这个问题，就是批改 TreeMap 的比拟函数逻辑：

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 == N) return N - 1 - x;
    // 中点和端点之间的长度
    return (y - x) / 2;
}

这样，[0,4] 和 [4,9] 的 distance 值就相等了，算法会比拟二者的索引，取较小的线段进行宰割。到这里，这道算法题目算是齐全解决了。

四、最初总结

本文聊的这个问题其实并不算难，尽管看起来代码很多。外围问题就是考查有序数据结构的了解和应用，来梳理一下。

解决动静问题个别都会用到有序数据结构，比方均衡二叉搜寻树和二叉堆，二者的工夫复杂度差不多，但前者反对的操作更多。

既然均衡二叉搜寻树这么好用，还用二叉堆干嘛呢？因为二叉堆底层就是数组，实现简略啊，详见旧文「二叉堆详解」。你实现个红黑树试试？操作简单，而且耗费的空间相对来说会多一些。具体问题，还是要抉择失当的数据结构来解决。

心愿本文对大家有帮忙。