这周的限时大模拟碰到一道非常经典的“团队聚会”题题面很短但信息密度很高一群人分别给出自己的若干忙碌时间段要在给定时间范围内找出所有能让全员一起开会、并且持续时间至少 h 小时的连续空闲时间。第一次看到这种题很多人第一反应是“直接枚举每个小时不就行了”真正动手后才发现绝大多数时间都耗在了和时间格式、区间开闭、边界条件作斗争上。这篇文章就把这类时间区间题从建模到落地的完整过程拆开讲一遍适合正在刷区间合并、限时模拟题或者被“时间格式化输出”折磨过的同学参考。1. 题目到底在考什么从场景到问题抽象1.1 把“团队聚会”翻译成区间模型先别急着写代码先用数学语言重新描述一遍需求。每个人有几个忙碌时间段比如 A 在04/01 08:00 ~ 09:00忙B 在04/01 08:30 ~ 10:00忙。注意B 的忙碌区间覆盖了 A 的空闲时间09:00 ~ 09:30所以虽然 A 那段时间有空但 B 没空团队聚会依然开不成。整个团队能开会的充要条件是这个时间段内没有任何一个人在忙。翻译成集合语言就是先把所有人的忙碌区间求并集得到“全局忙碌集合”。然后在整个时间轴上取这个集合的补集补集里的每个连续段才是所有人都有空的候选时间。最后再筛掉长度小于h * 60分钟的段剩下的就是答案。这里有一个非常容易绕晕的点不能把每个人的空闲区间分别算出来再做交集。因为一个人可能一天被繁忙区间切成了好几段每段的边界不一样“先把每个人的空闲段找出来再求交集”虽然逻辑上可行但实现起来要多维护一层结构而且处理交接点的时候非常容易漏掉边界分钟。直接合并全局忙碌区间再取补集是当时我调试下来最省心的一条路。1.2 典型输入输出长什么样这类题的数据格式通常比较固定但也正因为固定一旦某个细节踩错就是整题白给。先说输入第一行是 T 组数据。每组数据里第一行是人数 n接下来 n 行描述每个人的忙碌时段。每行的开头是一个整数 m表示这个人的忙碌时段数量然后跟着 m 个时段。每个时段由 8 个整数组成顺序一般是“开始月、开始日、开始小时、开始分钟、结束月、结束日、结束小时、结束分钟”。最后一行是一个整数 h表示会议最少持续的小时数。输出格式常见的是每组先输出Scenario #x:然后按时间顺序输出每个可行时间段格式类似appointment possible from 04/01/08:00 to 04/01/10:00如果没有可行时间就输出no appointment possible。不同题源的输出措辞可能会有细微差异但“场景编号 时间段列表 空结果提示”这个骨架基本不会变。限时模拟里这种题型的数据量一般不大难的不是复杂度而是“把原始输入准确转换成内部表示再把内部表示准确转换回题目要求的格式”。我在实际做的时候第一步永远是确认时间范围从哪里开始、到哪里结束这决定了后面哨兵区间怎么放。2. 方案选型合并忙区间是最稳的路线2.1 为什么不用差分扫描线很多人看到区间覆盖第一反应是差分数组加扫描线每个繁忙区间在起点 1在终点 -1然后从左到右扫一遍覆盖数为 0 的段就是空闲段。这个思路本身没错但实际写的时候很容易在“同一时刻有多个事件”上翻车。举个例子A 的忙区间是[08:00, 09:00)B 的忙区间是[09:00, 10:00)。如果按照半开区间处理09:00这个时刻既是一个结束事件也是一个开始事件。扫描线如果先处理-1再处理1那在09:00这一瞬间覆盖数会先变成 0 再变成 1看起来好像有一瞬间空闲实际上并没有可用的空隙。如果先处理1再处理-1虽然最终结果可能碰巧对但代码的语义会变得非常微妙必须靠注释和测试用例反复确认。更麻烦的是差分扫描线需要把“关键点之间的整段区间”作为考察单元。如果某个空闲段很长长到中间没有任何关键点代码必须正确输出整段而不是只输出关键点附近的碎片。这要求你对离散化的端点处理非常严谨否则一整段超长时间会被静默漏掉。每次限时模拟时间都很紧我不想在这种“顺序依赖”的边界问题上赌自己的状态所以果断放弃了差分路线。2.2 区间合并补集法为什么更省心区间合并补集法的步骤非常机械基本不存在事件顺序的歧义把所有繁忙区间丢进同一个数组。按开始时间排序。线性扫描把重叠的区间合并成一个。两个合并后的忙区间之间如果有空隙那就是全员空闲段。过滤掉长度不足的段输出。因为第一步到第三步处理的是“并集”的语义后一步直接在并集上找洞不需要关心某个时刻同时发生几个事件的先后顺序。代码短逻辑直白调试的时候只要打印出每一步的区间列表基本一眼就能看出问题在哪。复杂度上假设 n 最多 20 人每个人最多 100 个时段全部区间数也不会超过 2000排序一次也就毫秒级。哪怕是限时模拟这种复杂度也完全不需要优化。我当时算了一下直接把所有区间塞进vector排序合并比任何“优化”都更不容易写错。3. 核心实现时间转换、区间合并与答案输出3.1 时间数字化先算好月份前缀要做区间运算第一步是把04/01 08:00这种人类友好格式转换成整数。最稳妥的单位是“从当年 1 月 1 日 00:00 起到该时刻的分钟数”。转换公式是(monthPrefix[month - 1] day - 1) * 1440 hour * 60 minute这里的monthPrefix[i]表示从 1 月到 i 月的天数累加值。比如 4 月 1 日monthPrefix[3]是 1 月到 3 月的总天数加上day - 1得到从年初到 4 月 1 日之前的天数再乘以 1440 转成分钟。为什么是day - 1因为 1 月 1 日对应的天偏移量是 0不是 1这个细节写错一次所有时间都会偏一天。月份天数表我习惯用平年0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31如果题目输入可能出现02/29那就把 2 月改成 29 天然后重新算前缀表。这类题一般默认不跨年、不涉及闰年但保险起见我会在代码注释里留一句“如果是闰年场景请自行调整”避免自己拿到一个变体题时想不起来。3.2 左闭右开区间一个约定决定成败时间区间到底怎么定义边界是这道题最容易 WA 的地方。我强烈建议统一使用左闭右开区间[l, r)含义是从 l 分钟开始忙到 r 分钟之前这一整段都算忙r 这一分钟不算忙。如果题目明确写了“结束时间包含在忙碌时间段内”那读入结束时间后对结束分钟数做一次1转成左闭右开再存。为什么要这么折腾因为半开区间可以天然避免“整点边界到底归谁”的争议。比如 A 忙08:00 ~ 09:00B 忙09:00 ~ 10:00。如果都按闭区间理解09:00这个点既包含在 A 的结束里又包含在 B 的开始里到底算不算空闲就说不清。转成左闭右开后A 是[08:00, 09:00)B 是[09:00, 10:00)中间没有任何空隙语义完全一致后续判断也不会模棱两可。还有一个小细节读入繁忙时段时顺手过滤掉r l的零长度区间。这种区间可能是输入本身就有问题也可能是因为题目允许的边界条件产生退化段。如果不过滤合并时它会把空闲段凭空切断导致输出多出很多不应存在的分割点。我第一次提交就在这个不起眼的地方栽了跟头。3.3 哨兵区间与合并规则时间轴的左端和右端都要放“隐形的哨兵”。左边从 0 开始代表 1 月 1 日 00:00右边的总边界设置为totalMin monthPrefix[12] * 1440也就是 12 月 31 日 24:00 对应的分钟数。如果没有右哨兵最后一个空闲段如果一直延伸到年末就永远不会被输出。没有左哨兵同理年初到第一个繁忙区间之间的空闲段也会丢。合并规则本身很简单如果当前段的左端点大于已合并段的右端点说明两者之间有缝隙开启新的合并段。否则扩展已合并段的右端点为两者的较大值。我习惯在代码里写成s.l merged.back().r作为“不重叠”的判断条件因为两个半开区间首尾相接时s.l merged.back().r应被视为连续段这样不会产生长度为 0 的缝隙判断。3.4 输出格式化一个容易白给的环节输出是最容易被扣分的地方原因很现实时间要补零而且补零的位数必须是两位。比如04/01/08:00月、日、时、分都要%02d少一个零就是格式错误。从分钟数反解日期时我先把总分钟数除以 1440 得到“从年初起的天偏移量”再用月份前缀表反推月份和日期。这里同样要注意day 1 monthPrefix[month]的判断顺序不然遇到月初、月末交界点很容易错位。小时和分钟则通过对1440取余后分别除以 60 得到。还有一个很多人没注意过的坑右边界totalMin对应的时间其实是下一年的01/01/00:00直接按常规函数反解会越界。我的处理是在输出函数里对t totalMin做特判直接按题目允许的“年末结束”语义打印。有的题源接受01/01/00:00这种写法有的要求显示成12/31/23:59务必以你拿到的题面为准。判断可行段时用内部分钟数比较不要被输出形式干扰。4. 手把手调试一组样例4.1 构造一份直观的测试数据光说不练没有用我拿一个简单但覆盖关键点的例子走一遍完整流程。假设有两个人A忙04/01 08:00 ~ 09:0004/01 14:00 ~ 15:00B忙04/01 08:30 ~ 10:0004/01 15:00 ~ 16:00会议时长先设为 1 小时把所有繁忙区间转成分钟并排序后得到四个左闭右开区间开始时间结束时间说明04/01 08:0004/01 09:00A 的第一个忙段04/01 08:3004/01 10:00B 的第一个忙段04/01 14:0004/01 15:00A 的第二个忙段04/01 15:0004/01 16:00B 的第二个忙段前两个区间重叠合并成[08:00, 10:00)。后两个区间首尾相接合并不合并都不影响空闲判断合并后是[14:00, 16:00)。4.2 找补集并判断时长从年初 0 开始第一个合并忙区间从08:00开始所以年初到08:00之间是空闲段长度 480 分钟满足 1 小时条件。接着[10:00, 14:00)也是空闲段长度 240 分钟满足。最后[16:00, 年末)是空闲段长度远大于 60 分钟也满足。于是会输出三条结果Scenario #1: appointment possible from 01/01/00:00 to 04/01/08:00 appointment possible from 04/01/10:00 to 04/01/14:00 appointment possible from 04/01/16:00 to 01/01/00:00如果把会议时长改成 5 小时第二条空闲段只有 240 分钟不够 300 分钟就会被过滤掉只剩第一条和第三条。这个例子虽然简单但覆盖了“区间重叠”“首尾相接”“首尾哨兵”“时长过滤”这几个主要考点。我在本地调代码时永远会准备一组这样的手算数据比随机大数据有用得多。5. 常见问题与排查技巧踩坑实录我把自己和周围人经常踩的坑整理成一个速查表方便你对着排查症状可能原因解决办法输出结果整体少一段忘了设置时间轴首尾哨兵左边界从 0 开始右边界设一整年总分钟数边界整点的时间判断总出错忙区间用了闭区间或左右开闭不一致统一转成左闭右开结束时间必要时1输出时间串少 0格式化用了%d而不是%02d月、日、时、分全部两位补零月份总是差一个月前缀表下标或day - 1处理错误用 1 月 1 日手动跑一遍转换函数验证多组数据之间互相污染vector没有在每组清空每组开头重新定义局部vector出现“不可能存在的多出来的分割点”零长度忙区间没有过滤读入时只保留r l的区间最后一个空闲段显示成跨年时间右边界反解越界特判t totalMin的输出格式明明有空闲段却被判为无解忙区间合并时没有正确更新右端点合并时用max(右端点, 当前段右端点)调试顺序也有讲究。我拿到一个 WA 后不会直接看大样例而是先在每个关键步骤打印中间结果打印所有繁忙区间转换后的分钟区间。打印排序合并后的结果。打印每个空闲段及其长度。这三行打印出来问题基本就定位了。尤其要检查“合并后的忙区间是否出现了重叠”和“空闲段长度是否与手算一致”。这类限时模拟题最大的敌人不是算法不会而是边界条件在你没注意的地方悄悄漏了一拍。6. 完整代码模板可直接抄作业下面给出我调通的完整代码注释里保留了最容易踩的几个坑。totalMin和printTime之间的边界特判不要删否则最后一组输出很可能会数组越界。#include bits/stdc.h using namespace std; const int DAY_MIN 24 * 60; int monthDay[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int monthPre[13]; int totalMin; struct Seg { int l, r; // 左闭右开 [l, r) }; // 把 月/日/时/分 转成从 1月1日00:00 起的分钟数 int toMinute(int mo, int d, int h, int mi) { return (monthPre[mo - 1] d - 1) * DAY_MIN h * 60 mi; } // 反向输出注意 totalMin 需要特判 void printTime(int t) { if (t totalMin) { printf(01/01/00:00); return; } int dayOffset t / DAY_MIN; int rem t % DAY_MIN; int mo 1; while (mo 12 dayOffset 1 monthPre[mo]) { mo; } int dd dayOffset 1 - monthPre[mo - 1]; int hh rem / 60; int mm rem % 60; printf(%02d/%02d/%02d:%02d, mo, dd, hh, mm); } int main() { for (int i 1; i 12; i) { monthPre[i] monthPre[i - 1] monthDay[i]; } totalMin monthPre[12] * DAY_MIN; int T; scanf(%d, T); for (int tc 1; tc T; tc) { int n; scanf(%d, n); vectorSeg busy; for (int i 0; i n; i) { int m; scanf(%d, m); for (int j 0; j m; j) { int a, b, c, d, e, f, g, h; scanf(%d%d%d%d%d%d%d%d, a, b, c, d, e, f, g, h); int l toMinute(a, b, c, d); int r toMinute(e, f, g, h); // 如果题面说明结束时刻也属于忙碌时间这里执行 r if (r l) { busy.push_back({l, r}); } } } int needHours; scanf(%d, needHours); int needMin needHours * 60; sort(busy.begin(), busy.end(), [](const Seg x, const Seg y) { if (x.l ! y.l) return x.l y.l; return x.r y.r; }); vectorSeg merged; for (auto s : busy) { if (merged.empty() || s.l merged.back().r) { merged.push_back(s); } else { merged.back().r max(merged.back().r, s.r); } } printf(Scenario #%d:\n, tc); bool found false; int cur 0; for (auto s : merged) { if (s.l cur) { int len s.l - cur; if (len needMin) { found true; printf(appointment possible from ); printTime(cur); printf( to ); printTime(s.l); printf(\n); } } cur max(cur, s.r); } if (totalMin cur) { int len totalMin - cur; if (len needMin) { found true; printf(appointment possible from ); printTime(cur); printf( to ); printTime(totalMin); printf(\n); } } if (!found) { printf(no appointment possible\n); } } return 0; }这段代码可以直接跑通大多数以“按整年找空闲”为背景的团队聚会题。如果你的题面把时间范围限制成了某个具体区间比如从04/01到04/10就把左右哨兵改成对应的开始和结束分钟数输出函数里的边界特判同样适用。7. 这类限时模拟题怎么稳定拿分限时模拟和平时刷题最大的不同是你只有两三个小时必须把“犯错成本”压到最低。以我个人的习惯拿到这种题后的顺序是先花十分钟把题面完整读三遍确认时间范围、区间语义和输出格式再用笔在草稿纸上把样例转成分钟手算一遍预期输出最后才开始写代码。写代码时也要给自己留退路。比如我上面代码中用了vectorSeg而不是裸数组虽然运行效率略低一点但换来了“不用预判最大区间数”的安全感。输出部分能用printf就不用cout因为%02d的补零格式实在太好用了cout还要配setw和setfill在限时状态下更容易出错。最后再分享一个我踩过几次坑之后总结的小技巧所有时间相关的中间变量全部用分钟整数表示不要混合着“月日时分”和“分钟”做比较。你要比较两个时刻的大小就都转成分钟你要输出结果就只在最后一刻调用格式化函数。这样能最大程度减少人为换算带来的混乱。限时模拟考的不只是你会不会算法更多的是在压力下能不能守住每一处细节。团队聚会这道题就是一个典型例子模型不难难的是把各种边界都照顾周全。