如何调度考生的座位

labuladong约 4727 字大约 16 分钟数据结构设计

Info

数据结构精品课open in new window 和递归算法专题课open in new window 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》open in new window 出版，签名版限时半价！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
855. Exam Roomopen in new window	855. 考场就座open in new window	🟠

本文讲一讲力扣第 855 题「考场就座open in new window」，有趣且具有一定技巧性。这种题目并不像动态规划这类算法拼智商，而是看你对常用数据结构的理解和写代码的水平，个人认为值得重视和学习。

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

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

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

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

class ExamRoom {
    // 构造函数，传入座位总数 N
    public ExamRoom(int N);
    // 来了一名考生，返回你给他分配的座位
    public int seat();
    // 坐在 p 位置的考生离开了
    // 可以认为 p 位置一定坐有考生
    public void leave(int p);
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class ExamRoom {
public:
    // 构造函数，传入座位总数 N
    ExamRoom(int N);
    // 来了一名考生，返回你给他分配的座位
    int seat();
    // 坐在 p 位置的考生离开了
    // 可以认为 p 位置一定坐有考生
    void leave(int p);
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class ExamRoom:
    
    def __init__(self, N: int):
        """
        构造函数，传入座位总数 N

        :type N: int
        """
        pass
    
    def seat(self) -> int:
        """
        来了一名考生，返回你给他分配的座位

        :rtype: int
        """
        pass
    
    def leave(self, p: int) -> None:
        """
        坐在 p 位置的考生离开了
        可以认为 p 位置一定坐有考生

        :type p: int
        :rtype: void
        """
        pass

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type ExamRoom struct{}

// 构造函数，传入座位总数 N
func Constructor(N int) ExamRoom {}

// 来了一名考生，返回你给他分配的座位
func (er *ExamRoom) Seat() int {}

// 坐在 p 位置的考生离开了
// 可以认为 p 位置一定坐有考生
func (er *ExamRoom) Leave(p int) {}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var ExamRoom = function(N) {
    // 构造函数，传入座位总数 N
    this.N = N;
    this.seats = [];
};

// 来了一名考生，返回你给他分配的座位
ExamRoom.prototype.seat = function() {

};

// 坐在 p 位置的考生离开了
// 可以认为 p 位置一定坐有考生
ExamRoom.prototype.leave = function(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 就是一个有序集合，目的就是为了保持线段长度的有序性，快速查找最大线段，快速删除和插入。

二、简化问题

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

这个问题还用到一个常用的编程技巧，就是使用一个「虚拟线段」让算法正确启动，这就和链表相关的算法需要「虚拟头结点」一个道理。

class ExamRoom {
    // 将端点 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;
    }

    // ...
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class ExamRoom {
private:
    // 将端点 p 映射到以 p 为左端点的线段
    unordered_map<int, vector<int>> startMap;
    // 将端点 p 映射到以 p 为右端点的线段
    unordered_map<int, vector<int>> endMap;
    // 根据线段长度从小到大存放所有线段
    set<vector<int>> pq;
    int N;

public:
    ExamRoom(int N) {
        this->N = N;
        startMap = unordered_map<int, vector<int>>();
        endMap = unordered_map<int, vector<int>>();
        pq = set<vector<int>>([](vector<int> a ,vector<int> b) -> bool {
            // 算出两个线段的长度
            int distA = (a[1] - a[0]) / 2;
            if(a[0] == -1) distA = a[1];
            int distB = (b[1] - b[0]) / 2;
            if(b[0] == -1) distB = b[1];
            // 长度更长的更大，排后面
            return distA > distB || (distA == distB && a[0] < b[0]);
        });
        // 在有序集合中先放一个虚拟线段
        addInterval(vector<int>{-1, N});
    }

private:
    /* 去除一个线段 */
    void removeInterval(vector<int> intv) {
        pq.erase(intv);
        startMap.erase(intv[0]);
        endMap.erase(intv[1]);
    }

public:
    /* 增加一个线段 */
    void addInterval(vector<int> intv) {
        pq.insert(intv);
        startMap[intv[0]] = intv;
        endMap[intv[1]] = intv;
    }

private:
    /* 计算一个线段的长度 */
    int distance(vector<int> intv) {
        return (intv[1] - intv[0]) / 2;
    }

public:
    // ...
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class ExamRoom:
    def __init__(self, N: int):
        self.N = N
        # 将端点 p 映射到以 p 为左端点的线段
        self.startMap = {}
        # 将端点 p 映射到以 p 为右端点的线段
        self.endMap = {}
        # 根据线段长度从小到大存放所有线段
        self.pq = SortedSet(key=lambda x: (x[1]-x[0]-1,x[0]))
        # 在有序集合中先放一个虚拟线段
        self.addInterval([-1,N])
    
    # 去除一个线段
    def removeInterval(self,intv: List[int]) -> None:
        self.pq.remove(intv)
        del self.startMap[intv[0]]
        del self.endMap[intv[1]]
            
    # 增加一个线段
    def addInterval(self,intv: List[int]) -> None:
        self.pq.add(intv)
        self.startMap[intv[0]] = intv
        self.endMap[intv[1]] = intv
    
    # 计算一个线段的长度
    def distance(self,intv: List[int]) -> int:
        return intv[1]-intv[0]-1
        
    # ...

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type ExamRoom struct {
    // 将端点 p 映射到以 p 为左端点的线段
    startMap map[int][]int
    // 将端点 p 映射到以 p 为右端点的线段
    endMap map[int][]int
    // 根据线段长度从小到大存放所有线段
    pq *tree.Set
    N int
}

func Constructor(N int) ExamRoom {
    this := ExamRoom{}
    this.N = N
    this.startMap = make(map[int][]int)
    this.endMap = make(map[int][]int)
    this.pq = tree.NewWith(func(a, b interface{}) int {
        intv1, intv2 := a.([]int), b.([]int)
        distA, distB := distance(intv1), distance(intv2)
        // 长度更长的更大，排后面
        if distA == distB {
            return intv1[0] - intv2[0]
        }
        return distB - distA
    })
    // 在有序集合中先放一个虚拟线段
    this.addInterval([]int{-1, N})
    return this
}

/* 去除一个线段 */
func (this *ExamRoom) removeInterval(intv []int) {
    this.pq.Remove(intv)
    delete(this.startMap, intv[0])
    delete(this.endMap, intv[1])
}

/* 增加一个线段 */
func (this *ExamRoom) addInterval(intv []int) {
    this.startMap[intv[0]] = intv
    this.endMap[intv[1]] = intv
    this.pq.Add(intv)
}

/* 计算一个线段的长度 */
func distance(intv []int) int {
    return intv[1] - intv[0] - 1
}

// ...

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

/**
 * @param {number} N
 */
var ExamRoom = function(N) {
    // 将端点 p 映射到以 p 为左端点的线段
    this.startMap = new Map();
    // 将端点 p 映射到以 p 为右端点的线段
    this.endMap = new Map();
    // 根据线段长度从小到大存放所有线段
    this.pq = new TreeSet((a, b) => {
        // 算出两个线段的长度
        var distA = distance(a);
        var distB = distance(b);
        // 长度更长的更大，排后面
        return distA - distB;
    });
    this.N = N;
    // 在有序集合中先放一个虚拟线段
    this.addInterval([-1, N]);
};

/**
 * 去除一个线段
 * @param {number[]} intv
 */
ExamRoom.prototype.removeInterval = function(intv) {
    this.pq.delete(intv);
    this.startMap.delete(intv[0]);
    this.endMap.delete(intv[1]);
};

/**
 * 增加一个线段
 * @param {number[]} intv
 */
ExamRoom.prototype.addInterval = function(intv) {
    this.pq.add(intv);
    this.startMap.set(intv[0], intv);
    this.endMap.set(intv[1], intv);
};

/**
 * 计算一个线段的长度
 * @param {number[]} intv
 * @return {number}
 */
ExamRoom.prototype.distance = function(intv) {
    return intv[1] - intv[0] - 1;
};

// ...

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

有了上述铺垫，主要 API seat 和 leave 就可以写了：

class ExamRoom {
    // ...

    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 函数，不能简单地让它计算一个线段两个端点间的长度，而是让它计算该线段中点和端点之间的长度。

class ExamRoom {
    // ...

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

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class ExamRoom {
    // ...

    private:
        int distance(vector<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;
        }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class ExamRoom:
    # ...

    def distance(self, intv: List[int]) -> int:
        x, y = intv[0], intv[1]
        if x == -1:
            return y
        if y == N:
            return N - 1 - x
        # 中点和端点之间的长度
        return (y - x) // 2

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type ExamRoom struct {
    // ...
}

func (this *ExamRoom) distance(intv []int) int {
    x := intv[0]
    y := intv[1]
    if x == -1 {
        return y
    }
    if y == len(this.seats) {
        return len(this.seats) - 1 - x
    }
    // 中点和端点之间的长度
    return (y - x) / 2
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var ExamRoom = function() {
    // ...

    var distance = function(intv) {
        var x = intv[0];
        var y = intv[1];
        if (x == -1) return y;
        if (y == N) return N - 1 - x;
        // 中点和端点之间的长度
        return Math.floor((y - x) / 2);
    }
}

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

四、最后总结

本文聊的这个问题其实并不算难，虽然看起来代码很多。核心问题就是考察有序数据结构的理解和使用，来梳理一下。

处理动态问题一般都会用到有序数据结构，比如平衡二叉搜索树和二叉堆，二者的时间复杂度差不多，但前者支持的操作更多。

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

希望本文对大家有帮助。

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释

# 一、思路分析

# 二、简化问题

# 三、进阶问题

# 四、最后总结

一、思路分析

二、简化问题

三、进阶问题

四、最后总结