P2161会场预约：用set与运算符重载解决区间相交判断

1. 从一道老题说起：会场预约到底在考什么

我第一次见到P2161 [SHOI2009] 会场预约，是在一个算法讨论群里。有人贴出题面：“有N个操作，每次可以预约一个时间段，或者取消预约，要求实时输出当前被取消的预约数。”乍一看是个区间维护问题，但真正动手做的时候才发现，这题的核心不在数据结构有多高级，而在一个很容易被忽略的细节——区间相交判断。而判断区间相交，又偏偏可以借着C++的运算符重载写得很优雅，这才是这题被很多人拿来练手的原因。

先说结论：这题适合的人群非常明确——正在学C++面向对象、想练STL set用法、或者准备NOIP/省选但不想碰线段树平衡树这类重武器的选手。它用到的核心知识点就三个：set的自定义排序与二分查找、区间相交的数学判断、以及operator<等运算符重载的实战写法。解决它不需要树状数组，不需要懒标记，甚至不需要离散化，一个普通set加几个自定义比较函数就能跑出不错的性能。

我当年做这题的时候，第一反应是“这不就是个线段树区间覆盖吗？”，结果看到数据范围和操作定义后冷静下来才意识到，题目的巧妙之处在于每删掉一个旧预约，新预约才能插入，这个逻辑天然适合用平衡树来模拟。而平衡树用什么实现？手写Treap？没必要。STL的set底层是红黑树，插入、删除、查找都是O(log n)，配合自定义类型的运算符重载，代码量可以压到很短，而且思路异常清晰。

这篇文章我就把这道题从题面到AC的完整过程拆开讲一遍。重点放在为什么区间相交判断要写成那样、重载运算符在set里到底扮演什么角色、以及哪些坑是只看题解根本学不到的。会用生活化的类比解释“为什么两个区间相交的条件是a.l <= b.r && b.l <= a.r”，也会给出我实际调试时踩过的三个典型的雷区。不管你是刚开始刷题的大学生，还是准备机试的职场人，这条思路都能直接迁移到很多区间类问题上。

2. 题目理解与核心思路拆解

2.1 题面背后的真实业务逻辑

SHOI2009这道题的场景很简单：一个会场管理员，不断收到“我要预约A到B时段”的请求。但会场管理有个硬性规则——任何两个预约不能时间重叠。比如某人预约了8:00-10:00，那别人就不能再预约9:00-11:00，也不能预约8:30-9:30，哪怕只撞了一分钟也不行。管理员每次收到新预约时，需要把跟新预约冲突的所有旧预约全部取消，然后才能安排新的。

这个“冲突即取消”的规则，正是这题最核心的行为逻辑。它对应到代码层面就是：在set中找出所有与待插入区间相交的区间，逐个删除，最后再插入新区间，并返回删除了几个。整个操作非常像一个“有冲突就顶掉”的占座机制——新来的强势预约会把所有和自己重叠的旧预约全部挤掉。这种场景在真实的会议室预订系统、订票系统里都很常见，所以这题不是单纯为了考算法而考算法，它的模型很贴近实际业务。

理解这一点之后，思路就清晰了：我们需要维护一个互不相交的区间集合。因为每次删除冲突区间之后，剩下的区间一定两两不交，否则它们早就在历史操作中互相顶掉了。正是这个“不交性”保证了我们可以用set来维护，不需要处理复杂的区间合并。

2.2 为什么特意强调“重载运算符”

很多第一次接触这题的人会问：我直接在set里存pair<int,int>，然后用pair默认的排序规则不行吗？表面上看，pair会先比较第一个元素再比较第二个元素，区间按左端点排序似乎也说得通。但问题来了——你不仅要排序，还要快速找到“与新区间相交的所有区间”，这需要自定义的比较逻辑。而且当你需要删除一个区间时，set会按比较函数去定位元素，如果比较函数只比较左端点，那两个左端点相同但右端点不同的区间会被当成同一个元素，直接导致插入失败。

这就是为什么要重载运算符。在C++里，set容器默认使用std::less比较元素，也就是调用operator<。如果你想让set的排序规则适合区间相交判断，就必须给区间类定义一套符合预期的operator<。这不仅仅是“为了好看”，而是set能正确定位、插入、删除的基础。

我见过不少同学试图用set<pair<int,int>>加自定义仿函数来绕过类定义，结果发现代码越写越绕，最后还是要回到封装一个区间类。实际上，封装成结构体并重载operator<是最符合直觉、也最不容易出错的方案。如果以后再遇到需要用set维护非标量类型的情况，这套思路可以直接复用——定义一个结构体，重载比较运算符，放进set，完事。

2.3 区间相交判断的数学本质

既然核心是区间相交，那就必须把相交判断的条件彻底搞清楚。两个区间[a.l, a.r]和[b.l, b.r]，什么时候相交？按直觉说就是“范围有重叠”。但计算机不能凭直觉判断，我们需要一个精确的表达式。

很多人第一反应是写四个条件：a.l <= b.r && a.r >= b.l，但这其实还是不严谨。正确的数学判断应该是：区间A在B的右边，意味着A的左端点大于B的右端点，即a.l > b.r；区间A在B的左边，意味着A的右端点小于B的左端点，即a.r < b.l。这两种情况都不相交。所以相交的补集就是：!(a.l > b.r || a.r < b.l)，即a.l <= b.r && a.r >= b.l。

这里有个细节容易混淆：闭区间用<=和>=，开区间用<和>。题面里“从时间A到时间B”通常表示闭区间，那么端点重合就算相交。比如有人预约了10:00-11:00，另一个人预约11:00-12:00，两个区间在11:00这个点重合了，这时候如果不特殊说明，那就视为冲突。我在实际做题时，一开始用<判断，结果样例答案不对，排查半天才发现是端点边界没处理好。

把这个条件记成公式就是：

两闭区间相交 ⇔ a.l <= b.r 且 a.r >= b.l

记住这个基本公式，后面所有代码逻辑都会围绕它展开。而在C++中，我们通常会把这个判断封装成一个成员函数，比如bool operator&(const Interval& other) const，不过在这题里，我们更需要的是借助运算符重载来让set执行“区间比较”，所以重点运算符其实是operator<。

3. 核心细节解析与实操要点

3.1 结构体设计与运算符重载的完整写法

先给出一个最经典的区间结构体定义，以及配套的运算符重载。这段代码看起来简单，但每个细节都有讲究。

struct Interval { int l, r; // operator<：定义set中的排序规则 bool operator< (const Interval& other) const { if (l != other.l) return l < other.l; return r < other.r; } // 判断两个区间是否相交 bool isIntersect(const Interval& other) const { return l <= other.r && r >= other.l; } };

这里operator<的逻辑很简单：先按左端点从小到大排，左端点相同就按右端点从小到大排。这样set中所有区间都按左端点有序，方便我们定位查找。但要注意，这个排序规则并不是“完美”的，它只保证了区间是不同元素，没有刻意去维护某种“区间不重叠且靠左排序”的形态。你可能会问：既然set中所有区间互不相交，为什么排序规则不直接设计成“按左端点排序即可”？因为如果只写return l < other.l，那当两个区间左端点相同时，operator<在两个方向上都会返回false，也就是说!(a<b) && !(b<a)成立，set会把它们视为“等价”，从而不允许两个相同左端点、不同右端点的区间同时存在。这显然不符合要求。

所以必须加上右端点的次级比较。这是一个非常容易踩的坑——当你自定义set的元素类型时，一定不能让不相等元素在比较器中“等价”。所谓等价，是指!(a<b) && !(b<a)。一旦出现这种情况，set会认为它们是重复元素，后插入的会被静默丢弃。

3.2 为什么用set而不是priority_queue或vector

先把这几种常见方案摆出来对比一下，你就明白set的优势了。

如果直接开vector存所有区间，每次新预约进来就线性扫描所有旧预约，逐个判断相交并删除，这样做代码最简单，但操作次数一多就会超时。这题的N可以达到10^5级别，O(N^2)在极限数据下完全跑不动。而线段树、树状数组虽然也能维护区间覆盖，但需要额外处理离散化、区间标记等问题，杀鸡用牛刀。

set是性价比最高的选择：红黑树保证有序，自带lower_bound和erase，插入删除的复杂度都是O(log n)。而我们要做的，其实就是利用红黑树的有序性，快速定位到“第一个可能与新区间相交的区间”，然后从这个位置开始往后扫描，直到遇到完全在新区间左侧的区间为止。整个操作下来，每个区间至多被插入一次、删除一次，均摊复杂度是O(n log n)，非常稳。

3.3 确定性的扫描起点：lower_bound的花式用法

核心操作可以拆成三步。

第一步，构造一个用于二分查找的“哨兵区间”。因为set的lower_bound依赖于operator<，如果我们想找到所有左端点小于某个值的区间，最简单的办法是构造一个左端点等于目标值的哨兵对象。例如，对于新区间[a, b]，我们想找到第一个左端点不小于a的区间，就构造一个tmp = Interval{a, -1}，然后调用it = st.lower_bound(tmp)。为什么右端点取-1？因为当左端点相等时，operator<会继续比较右端点，-1小于任何正常右端点，所以这个哨兵在所有左端点为a的区间里排在“最前面”，lower_bound能正确定位到第一个左端点不小于a的区间。

第二步，从it开始往后扫描。注意，it也可能恰好指向一个左端点小于a但右端点大于a的区间，这种情况怎么办？不用担心，因为我们会在循环里先判断“当前区间是否与新区间相交”，如果相交就删除，否则就判断它是否已经在新区间的左侧。如果当前区间的右端点小于新区间的左端点，那它肯定不相交，而且由于set是有序的，这个区间之前的所有区间也都在新区间左侧，不可能相交，可以直接跳到下一个。

但这里有个前提：it必须指向“第一个可能与新区间相交”的区间。如果it指向的是第一个左端点不小于a的区间，那么它之前的区间可能有一个特别长，左端点小于a但右端点大于a，这个区间也跟新区间相交，但我们的it却错过了它。这确实是容易遗漏的边界情况。

所以更稳妥的做法是：it从st.lower_bound(Interval{a, -1})开始，先特判一下如果it != st.begin()，则把it往前移一个位置，保证不遗漏。也就是：

auto it = st.lower_bound(Interval{a, -1}); if (it != st.begin()) --it;

这个操作极其关键。很多题解里直接写lower_bound然后循环，遇到特殊情况就会WA。我第一次按简单思路写就漏掉了这种“区间左端点小于a但右端点大于a”的情况，结果连样例都过不了，专门加了--it才通。

第三步，在循环里不断判断“如果当前区间与新区间相交，则删除并计数；如果当前区间的左端点已经大于新区间的右端点，那之后的区间更不可能相交，直接break”。为什么可以这样提前退出？因为set按左端点递增排序，如果当前区间的左端点都大于新区间的右端点了，那后面所有区间的左端点只会更大，当然不可能和新区间相交。

3.4 运算符重载在set删除时的隐式调用

除了排序，operator<还在set的删除操作中扮演了重要角色。当我们调用st.erase(it)时，只需要迭代器即可，不涉及比较。但如果我们想用st.erase(key)按值删除，那就需要key与set中已有元素“等价”。什么是等价？!(a<b) && !(b<a)。所以如果你想直接构造一个和某个区间相等的结构体去删除它，那你构造的对象必须在operator<的两方向比较中和目标区间结果相等。

这又是一个容易忽略的细节。很多人会写st.erase({l, r})，但前提是set中确实存在左端点为l、右端点为r的区间，否则erase(key)会把所有与key等价的元素都删掉。如果两个区间左端点相同但右端点不同，由于operator<带了右端点比较，它们不会等价，所以不必担心误删。但是如果你的operator<里只比较左端点，那灾难就来了——erase一个左端点相同的区间，可能把另一个左端点相同但右端点不同的区间也带走了。

所以再次强调：一切自定义set排序都必须在operator<中包含足够的维度的比较，让每个不同元素严格可比。

4. 实操过程与完整代码实现

4.1 模拟数据推演：从样例看操作流程

先采用样例数据手推一遍，能帮助理解代码执行过程。假设有4个操作：

A 10 20 -> 成功，当前区间数1 A 15 25 -> 冲突，删除10 20，插入15 25，输出1 B -> 当前区间数1 A 5 10 -> 与15 25不相交？这里注意5-10和15-25不交，插入，当前区间数2

不过真实的样例输出我不贴了（你自己测即可），重点看状态变化。第一次预约肯定输出0，因为没有旧预约被删除。第二次预约会顶掉第一次预约，输出1。第三次如果预约5 10，它和15 25不交，输出0，set里有两个区间。第四次预约10 15，它会和5 10在10点重合，和15 25在15点重合，所以一进一出要删掉两个旧区间，输出2，然后插入10 15，最终set里只有一个区间。

这个推演过程能帮我们理解代码逻辑：判断相交用的是闭区间，所以端点重合也算冲突。

4.2 核心代码：set + 自定义结构体的AC方案

下面给出完整可运行的代码，这个版本我加了注释，尽量让大家看清每一步在干什么。

#include <bits/stdc++.h> using namespace std; struct Interval { int l, r; bool operator< (const Interval& other) const { if (l != other.l) return l < other.l; return r < other.r; } bool isIntersect(const Interval& other) const { return l <= other.r && r >= other.l; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; set<Interval> st; string op; while (n--) { cin >> op; if (op[0] == 'A') { int a, b; cin >> a >> b; Interval cur{a, b}; int cnt = 0; // 找到第一个可能相交的位置 auto it = st.lower_bound(Interval{a, -1}); if (it != st.begin()) --it; // 从该位置向后扫描 while (it != st.end()) { if (it->isIntersect(cur)) { // 与当前区间相交，删除 it = st.erase(it); ++cnt; } else if (it->l > b) { // 当前区间在新区间右侧，后面的都不可能相交 break; } else { // 当前区间在新区间左侧，继续向后找 ++it; } } st.insert(cur); cout << cnt << '\n'; } else { // B操作：输出当前区间总数 cout << st.size() << '\n'; } } return 0; }

这个代码看起来短，但已经包含了所有核心技巧。值得注意的地方：

• lower_bound(Interval{a, -1})用哨兵查找第一个左端点不小于a的区间，这里-1充当了最小的右端点，保证等价性判断正确。
• if (it != st.begin()) --it;是防止漏掉左端点小于a但右端点大于a的长区间。
• st.erase(it)返回下一个迭代器，避免删除元素后迭代器失效。
• 判断“当前区间在新区间右侧”用的是it->l > b，而不是it->r > b，因为即使当前区间的左端点大于b，它都不可能和新区间相交，可以安全退出。如果只判断右端点，就可能陷入无限循环。

4.3 为什么这样扫描不会超时：均摊分析

可能有人担心：如果每次都从begin()附近开始扫描，会不会退化成O(n^2)？不会。因为每次扫描要么删除了一个区间，要么就通过break提前退出。被删除的区间以后不会再出现，所以每个区间最多被删除一次。对于不删除的区间，也就是那些被扫描到但没相交的区间，它们的数量也有限，因为每次最多扫描到第一个右端点小于a（即左侧）和第一个左端点大于b（即右侧）的区间，中间所有的相交区间都被删除了，所以每步操作扫描的“未删除区间”数量是常数级别的（其实左侧一个、右侧一个）。因此整体的复杂度是O(n log n)。

用大白话说就是：每个人都可能被别人顶掉一次，但没人会被顶掉两次。每次预约最多把整个会场“清场”一次，而清场之后剩下的区间要么在新区间左面，要么在右面，扫描也就到此为止。

4.4 扩展：如果不重载运算符，能不能用lamda表达式

有些同学不喜欢在全局重载运算符，想用set的第三个模板参数传入仿函数。那也可以，代码会变成这样：

struct Cmp { bool operator()(const Interval& a, const Interval& b) const { if (a.l != b.l) return a.l < b.l; return a.r < b.r; } }; set<Interval, Cmp> st;

这种写法的效果和重载operator<完全等价，只是把比较逻辑从类型内部搬到了外部。个人建议：如果这个区间类型只在本项目里用，直接重载operator<最省事；如果可能在多个项目里复用，用独立的仿函数或operator<=>（C++20）会更干净。C++20的生命周期比较运算符<=>也可以用来自动生成所有比较运算符，但这题为了兼容性还是老老实实用operator<比较稳妥。

另外提醒一下，如果你本地编译器支持C++17，还可以用std::tie(l, r) < std::tie(other.l, other.r)简化写法，效果一样，但是拆解不明显，不推荐初学时用。

5. 常见问题与排查技巧实录

5.1 问题一：为什么我的set插入失败或者元素消失

这是最常见的坑，罪魁祸首多半是operator<没有区分右端点。如果你只写return l < other.l，那么当两个区间左端点相同、右端点不同的时候，它们会被认为“等价”，set直接拒绝插入第二个。表面上看起来像是“插入失败”，其实是被去重了。

排查方法很简单：写个测试程序插入{1,2}和{1,3}，然后输出set里元素个数，如果输出1，说明比较器有问题。

5.2 问题二：迭代器越界崩溃

这个出现在删除区间后继续使用旧迭代器。set的erase(it)会使被删除的迭代器失效，但其他迭代器不受影响。我们上面的代码用了it = st.erase(it)，这是C++11之后的特性，erase会返回下一个有效迭代器。如果你用老版本编译器，就只能保存下一个迭代器再删除。

另一种越界情况是在循环内部++it之后，循环条件判断时未检查是否为end()。比如你写while (true)然后++it; if (it == st.end()) break;，这种情况还好，但如果你在++it之后立即解引用it->...，那就会崩溃。写循环时最好把it != st.end()作为循环条件的一部分，然后在循环体内根据情况break。

5.3 问题三：端点相等的区间没有被视为相交

很多人会把相交条件写成l < other.r && r > other.l，也就是严格不等式。这在开区间下是对的，但这题是闭区间，端点重合也是冲突。我曾经因为这个WA了三次，后来想了个巧办法：直接把两个区间都加一，再用开区间判断，但那样改动太大，不如直接背下闭区间的条件l <= other.r && r >= other.l。

可以用生活例子辅助记忆：A同学订了1点到2点的会议室，B同学订了2点到3点，他们在2点整有一个“交接”，如果会议室的规则要求2点整必须清场，那这俩预约不冲突；但如果规则是“时间区间内一直占用”，那2点整就是冲突。本题默认后者，所以用<=和>=。

5.4 问题四：lower_bound定位不准，漏删了区间

如果你发现自己漏删区间，多半是因为没有做--it的特判。有一个典型场景：

已有区间[1, 100]和[200, 300]，新预约[50, 150]。此时lower_bound(Interval{50, -1})会指向[200, 300]，因为[1,100]的左端点1小于50。然后你从[200,300]开始扫描，它和[50,150]不相交，左端点200大于150，于是break——但是[1,100]其实已经被你错过了。加上--it之后，it会指向[1,100]，扫描时发现相交，删除，之后[200,300]与新区间不相交，退出，结果正确。

这个细节非常关键。做题时我甚至总结了一个口诀：“lower_bound先退一步，扫描起来不会漏”。

5.5 问题五：B操作输出一直不对

B操作要求输出当前会场预约的数量，直接st.size()即可。这没啥好说的，但如果TLE，很可能是因为你在B操作里也做了线性扫描，那就画蛇添足了。另外注意操作字符串首字母是A还是B，判断op[0]=='A'就行。如果操作里有空格或其他字符，要小心读入方式。

5.6 问题六：数据范围不开int导致溢出

题目数据范围一般不大，但时间值可能有10^9级别，所以用int足够。如果你习惯用long long也没错，只是要保证Interval结构体里字段类型一致。这里还有个小技巧：把构造哨兵时的-1改成INT_MIN也能用，但没必要。

5.7 实战优化：减少重复比较

如果觉得每次循环比较isIntersect有点慢，可以在进入循环前先用cur.l和cur.r做条件判断，减少函数调用。比如：

while (it != st.end()) { if (it->l <= b && it->r >= a) { ... } ... }

这样能少一次函数调用。其实对于这题的数据量，差别不大，但养成这种思维好习惯，以后遇到性能瓶颈时知道从哪里下手。

6. 这题还能怎么玩：从SHOI2009到实际工程

6.1 变体一：动态维护可用时段

如果把题目反过来，我们需要维护“所有空闲时段”，那就是一个区间合并问题了。每次有人取消预约，对应某个空闲区间需要合并。这时候可以用类似的数据结构，但维护的是一个空闲区间集合。核心还是区间相交判断，只是逻辑翻转一下。这道题的延伸价值就在于此——掌握了区间相交判断，很多会议调度、库存区间、IP地址分配问题都能切入。

6.2 变体二：不删除所有相交区间，而是保留优先级更高的预约

现实中更常见的场景是：新预约不一定能顶掉旧预约，而是要看优先级。比如老板的预约永远优先于普通员工的预约。这时我们需要给每个区间增加一个priority字段，在删除冲突时判断是否需要真的删除。这仍然可以在原有代码框架上扩展，只要在isIntersect不改变的情况下，额外增加一个优先级比较逻辑即可。

6.3 变体三：统计被顶掉的总次数

原题只输出当前操作顶掉了多少个，但有时我们需要统计所有历史中被顶掉的预约总数。这个加一个全局计数器就行。更有趣的是，还可以记录每个被删除的预约是哪个时间段，用来生成取消通知。这种工程化改造，往往就是从一道算法题过渡到实际业务系统的第一步。

我在实际开发中写过预约系统，底层的“冲突检测 + 覆盖插入”和这题几乎一样，只是数据存在数据库表里，需要用SQL的between条件判断，但核心思想完全通用。所以建议刷到这题时不要满足于AC，多想想你的实现能怎么变形，这样才能真正把题目的价值榨干。

7. 踩坑总结与经验沉淀

最后再系统梳理一遍这题真正值得记下来的经验，这些不是公式，而是我实际写代码时反复栽跟头得出的教训。

第一，自定义set类型时，比较器必须让不同的元素严格有序。所谓“严格”，就是不能出现!(a<b) && !(b<a)但a和b不是同一个值的情况。判断标准就是：把所有可能的区间映射到排序规则上，如果两个元素的所有属性值完全相同，才允许它们等价。凡是只比较部分字段的比较器，迟早会出事。

第二，区间相交判断闭区间用<=/>=，开区间用</>，先判断条件再写代码。我建议把多个判断合并成一个公式写清楚，而不是写一长串if，这样既不容易出错，也方便review。假设两个区间分别是[a,b]和[c,d]，闭区间相交的C++表达式a <= d && c <= b，你可以把c当作“另一个区间的左端点”，所以原式写l <= other.r && other.l <= r，这样更对称，也更好记。

第三，用set.lower_bound找范围时，必须考虑向前回退一个位置。这个坑不单是这道题有，任何用有序容器做“范围查找”时都可能遇到。原因是区间不像点一样可以用单个坐标比较，它有两个维度，而lower_bound只按一个维度（左端点）定位，另一维度的边界信息可能被忽略。

第四，善用st.erase(it)的返回值。C++11之后erase会返回被删除元素的下一个迭代器，这是简化代码的好工具。但是如果你用的是旧标准，建议先用auto next_it = next(it); st.erase(it); it = next_it;。

第五，数据结构和算法选型要综合考虑代码复杂度和时空开销。这题用set是最优解之一，但不是唯一解。我见过有人手写Treap、Splay来做，代码两百行，维护起来也费劲；也见过用vector暴力过的，但只能过一些小题数据。比赛时的时间有限，能用STL就用STL，把精力花在思路正确性上，而不是重复造轮子。

如果把这题的思路迁移到其他题目，我还有一个额外的小技巧：当你需要维护“互不相交区间集合”时，优先想到set加自定义operator<；当你需要维护“可合并区间集合”时，优先想到set合并后删除旧插入新；当你需要“区间连续覆盖”时，才考虑线段树和树状数组。不同数据结构之间的选择不是越高大上越好，而是最适合当前问题的才好。

最后分享一个我调试这类边界型题目的小习惯：准备一个简单的数据生成器，专门生成端点重合、左端点相同、长区间套小区间等极端情况，把它们一股脑丢进代码里测试。把这题AC之后，这个测试习惯一直留了下来，每写一个新的数据结构题都会用上。区间相关题，最常见的坑永远在边界，而边界问题，只有用极端数据才能逼出来。希望这篇文章能帮你把P2161背后的知识点吃透，下次再遇到区间相交判断、运算符重载、set自定义排序这类问题，能少踩几个坑，多一点底气。