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里存pairint,int然后用pair默认的排序规则不行吗表面上看pair会先比较第一个元素再比较第二个元素区间按左端点排序似乎也说得通。但问题来了——你不仅要排序还要快速找到“与新区间相交的所有区间”这需要自定义的比较逻辑。而且当你需要删除一个区间时set会按比较函数去定位元素如果比较函数只比较左端点那两个左端点相同但右端点不同的区间会被当成同一个元素直接导致插入失败。这就是为什么要重载运算符。在C里set容器默认使用std::less比较元素也就是调用operator。如果你想让set的排序规则适合区间相交判断就必须给区间类定义一套符合预期的operator。这不仅仅是“为了好看”而是set能正确定位、插入、删除的基础。我见过不少同学试图用setpairint,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也就是说!(ab) !(ba)成立set会把它们视为“等价”从而不允许两个相同左端点、不同右端点的区间同时存在。这显然不符合要求。所以必须加上右端点的次级比较。这是一个非常容易踩的坑——当你自定义set的元素类型时一定不能让不相等元素在比较器中“等价”。所谓等价是指!(ab) !(ba)。一旦出现这种情况set会认为它们是重复元素后插入的会被静默丢弃。3.2 为什么用set而不是priority_queue或vector先把这几种常见方案摆出来对比一下你就明白set的优势了。方案查找相交区间删除元素插入元素总体复杂度代码复杂度vector 遍历O(n)O(n)O(1)O(n^2)低set/红黑树O(log n)O(log n)O(log n)O(n log n)中线段树O(log n)O(log n)O(log n)O(n log n)高树状数组O(log n)O(log n)O(log n)O(n log n)高如果直接开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中已有元素“等价”。什么是等价!(ab) !(ba)。所以如果你想直接构造一个和某个区间相等的结构体去删除它那你构造的对象必须在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不交输出0set里有两个区间。第四次预约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; setInterval 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; } }; setInterval, Cmp st;这种写法的效果和重载operator完全等价只是把比较逻辑从类型内部搬到了外部。个人建议如果这个区间类型只在本项目里用直接重载operator最省事如果可能在多个项目里复用用独立的仿函数或operatorC20会更干净。C20的生命周期比较运算符也可以用来自动生成所有比较运算符但这题为了兼容性还是老老实实用operator比较稳妥。另外提醒一下如果你本地编译器支持C17还可以用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)这是C11之后的特性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类型时比较器必须让不同的元素严格有序。所谓“严格”就是不能出现!(ab) !(ba)但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)的返回值。C11之后erase会返回被删除元素的下一个迭代器这是简化代码的好工具。但是如果你用的是旧标准建议先用auto next_it next(it); st.erase(it); it next_it;。第五数据结构和算法选型要综合考虑代码复杂度和时空开销。这题用set是最优解之一但不是唯一解。我见过有人手写Treap、Splay来做代码两百行维护起来也费劲也见过用vector暴力过的但只能过一些小题数据。比赛时的时间有限能用STL就用STL把精力花在思路正确性上而不是重复造轮子。如果把这题的思路迁移到其他题目我还有一个额外的小技巧当你需要维护“互不相交区间集合”时优先想到set加自定义operator当你需要维护“可合并区间集合”时优先想到set合并后删除旧插入新当你需要“区间连续覆盖”时才考虑线段树和树状数组。不同数据结构之间的选择不是越高大上越好而是最适合当前问题的才好。最后分享一个我调试这类边界型题目的小习惯准备一个简单的数据生成器专门生成端点重合、左端点相同、长区间套小区间等极端情况把它们一股脑丢进代码里测试。把这题AC之后这个测试习惯一直留了下来每写一个新的数据结构题都会用上。区间相关题最常见的坑永远在边界而边界问题只有用极端数据才能逼出来。希望这篇文章能帮你把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里存pairint,int然后用pair默认的排序规则不行吗表面上看pair会先比较第一个元素再比较第二个元素区间按左端点排序似乎也说得通。但问题来了——你不仅要排序还要快速找到“与新区间相交的所有区间”这需要自定义的比较逻辑。而且当你需要删除一个区间时set会按比较函数去定位元素如果比较函数只比较左端点那两个左端点相同但右端点不同的区间会被当成同一个元素直接导致插入失败。这就是为什么要重载运算符。在C里set容器默认使用std::less比较元素也就是调用operator。如果你想让set的排序规则适合区间相交判断就必须给区间类定义一套符合预期的operator。这不仅仅是“为了好看”而是set能正确定位、插入、删除的基础。我见过不少同学试图用setpairint,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也就是说!(ab) !(ba)成立set会把它们视为“等价”从而不允许两个相同左端点、不同右端点的区间同时存在。这显然不符合要求。所以必须加上右端点的次级比较。这是一个非常容易踩的坑——当你自定义set的元素类型时一定不能让不相等元素在比较器中“等价”。所谓等价是指!(ab) !(ba)。一旦出现这种情况set会认为它们是重复元素后插入的会被静默丢弃。3.2 为什么用set而不是priority_queue或vector先把这几种常见方案摆出来对比一下你就明白set的优势了。方案查找相交区间删除元素插入元素总体复杂度代码复杂度vector 遍历O(n)O(n)O(1)O(n^2)低set/红黑树O(log n)O(log n)O(log n)O(n log n)中线段树O(log n)O(log n)O(log n)O(n log n)高树状数组O(log n)O(log n)O(log n)O(n log n)高如果直接开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中已有元素“等价”。什么是等价!(ab) !(ba)。所以如果你想直接构造一个和某个区间相等的结构体去删除它那你构造的对象必须在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不交输出0set里有两个区间。第四次预约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; setInterval 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; } }; setInterval, Cmp st;这种写法的效果和重载operator完全等价只是把比较逻辑从类型内部搬到了外部。个人建议如果这个区间类型只在本项目里用直接重载operator最省事如果可能在多个项目里复用用独立的仿函数或operatorC20会更干净。C20的生命周期比较运算符也可以用来自动生成所有比较运算符但这题为了兼容性还是老老实实用operator比较稳妥。另外提醒一下如果你本地编译器支持C17还可以用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)这是C11之后的特性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类型时比较器必须让不同的元素严格有序。所谓“严格”就是不能出现!(ab) !(ba)但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)的返回值。C11之后erase会返回被删除元素的下一个迭代器这是简化代码的好工具。但是如果你用的是旧标准建议先用auto next_it next(it); st.erase(it); it next_it;。第五数据结构和算法选型要综合考虑代码复杂度和时空开销。这题用set是最优解之一但不是唯一解。我见过有人手写Treap、Splay来做代码两百行维护起来也费劲也见过用vector暴力过的但只能过一些小题数据。比赛时的时间有限能用STL就用STL把精力花在思路正确性上而不是重复造轮子。如果把这题的思路迁移到其他题目我还有一个额外的小技巧当你需要维护“互不相交区间集合”时优先想到set加自定义operator当你需要维护“可合并区间集合”时优先想到set合并后删除旧插入新当你需要“区间连续覆盖”时才考虑线段树和树状数组。不同数据结构之间的选择不是越高大上越好而是最适合当前问题的才好。最后分享一个我调试这类边界型题目的小习惯准备一个简单的数据生成器专门生成端点重合、左端点相同、长区间套小区间等极端情况把它们一股脑丢进代码里测试。把这题AC之后这个测试习惯一直留了下来每写一个新的数据结构题都会用上。区间相关题最常见的坑永远在边界而边界问题只有用极端数据才能逼出来。希望这篇文章能帮你把P2161背后的知识点吃透下次再遇到区间相交判断、运算符重载、set自定义排序这类问题能少踩几个坑多一点底气。
 分配 C++ 类实例的未定义行为诊断)
