
Info
数据结构精品课 和 递归算法专题课 限时附赠网站会员,全新纸质书《labuladong 的算法笔记》 出版,签名版限时半价!
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
855. Exam Room | 855. 考场就座 | 🟠 |
本文讲一讲力扣第 855 题「考场就座」,有趣且具有一定技巧性。这种题目并不像动态规划这类算法拼智商,而是看你对常用数据结构的理解和写代码的水平,个人认为值得重视和学习。
另外说句题外话,很多读者都问,算法框架是如何总结出来的,其实框架反而是慢慢从细节里抠出来的。希望大家看了我们的文章之后,最好能抽时间把相关的问题亲自做一做,纸上得来终觉浅,绝知此事要躬行嘛。
先来描述一下题目:假设有一个考场,考场有一排共 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 和刷题全家桶:

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