“程序设计思维与实践”这门课最刺激的就是限时大模拟倒计时一挂教室里全是键盘声。Week10 的 B 题“团队聚会”就是那种一眼看上去很亲切、动起手来却坑坑洼洼的题——一群人的忙碌时间段摆在你面前让你找出一个所有人都能聚齐的时间窗。我第一次做的时候以为就是个区间求交集结果写了半小时样例过了提交全错。这次复盘把完整的思路、代码和踩过的坑都整理出来给准备这门课或者刷类似区间题的同学做个参考。这道题解决的本质问题很简单给定一个团队若干成员的忙碌时间段求出至少连续 h 小时的空闲窗口窗口中所有人都处于空闲状态。现实中对应的场景就是约会议室、约开组会、跨时区约电话会议算法课上则把它包装成限时模拟题。适合正在学程序设计、准备期中期末上机考试的同学看算法基础要求不高但细节极其考验人对边界条件的敏感度。1. 题目到底在问什么团队聚会的核心难点拆解1.1 读题时最容易漏掉的三条隐藏规则这题的难点不在算法在理解规则。我反复读题之后发现真正决定生死的往往不是区间合并有多复杂而是下面这几个细则。第一会议只能安排在一天的工作时间内通常是早上 8 点到下午 17 点之间。超过这个范围的时间统统不能用来开会哪怕数据显示所有人凌晨都有空也不作数。有些同学把时间轴做成全天 24 小时多算出来一大片“空闲区间”提交当然过不了。第二聚会时长必须大于等于 h 小时。不是只要有空隙就行这个空隙必须足够长。有人会在最后输出时判断“存在空闲时段”就直接输出了忽略了时长下限。更隐蔽的是题目往往要求“至少连续 h 小时”也就是说只多一分钟都算合格但差一分钟都不行。第三忙碌时间段的格式往往不是规整的整点。可能给出“09:00-12:00”这种也可能出现“08:30-09:00”这种跨小时、带半点的数据。读题不仔细的同学容易在字符串解析上翻车把“08:30”当成“8:30”处理后面所有的时间运算都被带偏。这几条规则合在一起意味着你得先把题目里的每一个字都抠明白再做数据建模。千万不要凭印象写代码。1.2 从“人的时间”到“分钟数组”怎么建立数据模型处理时间段类问题我最推荐的做法是把时间统一转成分钟数再用分钟数组作为统计桶。比如 8 点代表第 480 分钟9 点代表第 540 分钟17 点代表第 1020 分钟。这样做的原因很直接小时的加减乘除太容易出现借位、进位错误而分钟是唯一确定的整数直接比较和累加都没歧义。有了分钟数之后可以再开一个长度固定的数组初始化为 0表示“这个分钟有多少人处于忙碌状态”。每读入一个人的忙碌时间段就把这个区间内的所有分钟桶加 1。到后面我们只要扫描这个数组找连续的一段其中所有桶的值都是 0就说明这段时刻全员空闲。很多人会下意识觉得这种暴力标记法太笨想去差分数组、线段树但在这题的数据范围下分钟桶是最稳的。一天只有 1440 分钟即使只在工作时间内判断也才几百个桶哪怕嵌套循环遍历都完全能跑完。限时模拟里简单可靠比什么都重要。1.3 为什么说这道题是“区间题的试金石”团队聚会这道题看起来平平无奇但它把区间类问题里最常见的几个坑全部集中起来了——字符串解析、单位换算、区间开闭边界、数组扫描顺序、输出格式约束。你只要有一个环节处理不对结果就是满盘皆输。所以这道题的价值不在于让你学会什么高深算法而在于逼迫你建立“输入→建模→扫描→输出”的完整闭环思维。很多人能写出求交集的函数却没有考虑输出时如果不存在满足条件的时段应该打印什么。题目里的每一个输出分支都必须在编码前想清楚这正是限时模拟想训练的能力。2. 核心算法设计从暴力标记到区间合并的思路演进2.1 方案A直接按分钟标记忙碌状态最稳也最快以 C 为例首先定义一个int busy[1500]数组清零。然后对每个成员的每段忙碌时间用两个整数startMinute和endMinute表示起止分钟循环从startMinute到endMinute的前一分钟busy[i]。循环结束时只要再扫描一遍480到1020这些分钟统计连续busy[i] 0的最长长度判断是否大于等于h * 60就能得到答案。这个方法的时间复杂度是 O(人数 × 区间长度)但因为区间长度最多几百总体运算量很小实测下来非常快。它的另一个好处是逻辑透明出错时很容易通过纸上模拟找回现场。如果你在限时考试中一时想不到更优雅的区间合并法直接写这个都能拿高分。for (int t start; t end; t) { busy[t]; }注意这里的区间是左闭右开的即忙碌时间含头不含尾。假设某人 12:00 到 13:00 忙碌那么分钟 720 到 779 是他忙碌的时间而 780 分钟即 13:00 整他已经是空闲的了。这样处理之后判断空闲区间也采用同样的左闭右开规则就不容易出现边界差 1 的错误。2.2 方案B区间合并再求交集为什么容易写崩不讲武德一点的做法是把每个人的空闲区间算出来然后对所有人的空闲区间求交。听起来很合理但实现的时候要处理大量细节一个人一天有多段忙碌时间他的空闲区域可能是多个区间多个人做交集时又得保留所有区间端点排序后两两比较。稍不留神就把区间合并写成了区间嵌套越改越乱。这类问题在 ACM 套路里通常叫“区间覆盖与求交”标准解法是用扫描线维护当前覆盖人数。但这个解法对初学者的代码量不友好限时环境下很容易因为一个小 bug 卡死半小时。所以我建议不到万不得已不与它硬碰。2.3 时间计算的核心细节为什么统一用分钟数用分钟数最大的好处是带来整型运算的确定性。比如计算 “08:30 到 12:15 持续了多久”如果直接操作字符串你还得判断分钟位是否够减但转换成分钟就是 495 到 735差是 240一眼就知道是 4 小时。对时间窗口做加 30 分钟这类偏移也只是一次整数加法。另一个困扰新手的点是跨小时判断。例如空闲区间的开始是 11:45结束是 14:20直接用字符串比较“14:20 11:45”也能判断但要计算区间长度时无论如何都要换算成统一单位。与其绕弯子不如从最开始就把输入全部映射成分钟数后面的所有判断都基于整数。这也是我觉得这题最值得养成的习惯。int timeToMinute(string s) { int h stoi(s.substr(0, 2)); int m stoi(s.substr(3, 2)); return h * 60 m; }3. 完整实现C代码逐段拆解与验证3.1 输入解析读不对行后面全白费这类题的输入格式通常是多行文本第一行给出测试组数每组先给人数和时长 h然后逐行给人名和忙碌区间。原始输入可能长这样3 2 1 Alice 09:00-10:00 Bob 09:30-11:00其中第三行既有成员名字又有忙碌时间段中间可能用空格分隔时间段内部用-连接起止时刻。我习惯的处理方式是先把每一行整个读进来再用stringstream或find分割出名字和时间段再从时间段里用substr提取起止时间。这样做的好处是就算输入格式里有多个连续空格也能正常适应不容易因为匹配不到而读错行。注意一个细节如果一次测试有多个用例并且每个用例人数不同一定要记得在每个用例开始时重新初始化全部时间桶和成员信息。我见过不少同学把上一组的数据带到了下一组导致越到后面结果越离谱。3.2 忙碌区间标记与扫描判断核心代码就这么多下面给出一个可以直接抄作业的完整代码主体。这里的注释写得比较详细照着理解就够了。#include bits/stdc.h using namespace std; const int START 8 * 60; // 480 const int END 17 * 60; // 1020 int timeToMinute(string s) { int h stoi(s.substr(0, 2)); int m stoi(s.substr(3, 2)); return h * 60 m; } int main() { int T; cin T; while (T--) { int n, h; cin n h; int busy[1500] {0}; for (int i 0; i n; i) { string name, st, en; cin name st en; int l timeToMinute(st); int r timeToMinute(en); for (int t l; t r; t) { busy[t]; } } int bestStart -1, bestLen 0; int curStart -1, curLen 0; for (int t START; t END; t) { if (busy[t] 0) { if (curStart -1) { curStart t; curLen 1; } else { curLen; } if (curLen bestLen) { bestLen curLen; bestStart curStart; } } else { curStart -1; curLen 0; } } if (bestLen h * 60) { cout No time endl; } else { int startH bestStart / 60; int startM bestStart % 60; int endMinute bestStart bestLen; int endH endMinute / 60; int endM endMinute % 60; printf(%02d:%02d-%02d:%02d\n, startH, startM, endH, endM); } } return 0; }这段代码里最核心的是扫描部分。我用busy[t] 0判断该分钟全员空闲再用两个变量记录当前连续空闲段的起点和长度。每当遇到忙碌分钟就清空当前计数否则累加并尝试更新最大值。这样一趟扫描能得到最长的全员空闲窗口长度计算采用的是左闭右开的分钟桶表示。3.3 输出格式与特殊情况提前想清楚避免提交时后悔题目对输出格式的要求通常很死板。如果找到了可行聚会时间段要输出形如10:00-12:00的格式小时和分钟都必须占两位小时可能是 8 到 17 之间的数。如果找不到满足时长要求的时间段则要输出No time之类的固定字符串。我建议把输出的每一种情况都画在纸上对照一下尤其是跨小时窗口比如08:30-09:15分钟部分很容易丢掉前导零。还需要考虑一种特殊情况如果有多段长度相同且都满足要求的时间窗口应该选哪一段输出有些题面会规定选最早的那一段有些题面没有明说。稳妥的做法是扫描时只更新更长的窗口不因相同长度而覆盖这样保留的就是最早的最长窗口。大多数判题数据默认期望最早的时段这也符合人类安排会议的直觉。3.4 数据范围与复杂度的实际测算假设团队人数 n 最大为 20 人每个人的忙碌区间按照字符串读入单段长度最多约 9 小时即 540 分钟。标记阶段的总操作次数最多为 20 × 540 10800 次扫描阶段只有 540 次这样的计算负载对任何评测环境都是瞬间完成的。相比之下如果使用基于排序的扫描线算法需要把所有区间端点都收集起来排序复杂度为 O(M log M)其中 M 是区间端点总数。当 n 达到 10 万甚至百万级别时这种优势才会体现出来。作为一门程序设计课程的限时模拟题按分钟标记的暴力方法完全够用而且更容易让别人读懂你的思路。4. 限时模拟里的真实翻车现场常见错误与调试技巧整理4.1 边界差 1 的经典错误区间到底含不含结尾在 2.1 节里我已经强调左闭右开但实际编码时很多人还是会写成for (int t l; t r; t)。表面上看无非是多标记了一分钟输出的空闲窗口会因此少一分钟在恰好卡在临界长度时就会从“合规”变“不合规”。举例来说某团队成员 12:00 到 13:00 忙碌聚会要求至少 1 小时。正确理解下 13:00 到 14:00 是完整的空闲时段可以开会。如果写错成那么 13:00 这一分钟也被标记成忙碌从 13:00 开始的连续空闲从 60 分钟变成 59 分钟于是正确答案被硬生生判成 No time。这种错误最可怕因为样例往往覆盖不到这种恰好差一分钟的情况。4.2 忙碌区间合并与多小时段输入的隐藏陷阱题面可能给每个成员不止一个忙碌区间。比如某同学早上 9:00 到 10:00 有课下午 14:00 到 15:00 有实验。此时需要把两段都标记到时间桶里而不是只保留最后读入的那一段。我见过一种常见的偷懒写法用一个整型数组保存每个成员最早忙碌时间和最晚忙碌时间默认成员全天忙碌只有一个连续大区间。这种做法在成员忙碌时间不连续时会导致空闲窗口计算错误。因为中间那段无人忙碌但有人其实忙着别的时间或者有人的忙碌区间被错误扩充结果自然不对。正确做法是严格逐段标记。不要试图用一个人最早的忙碌开始时间和最晚的忙碌结束时间构造一整段“忙碌区间”除非题目明确说每个人的忙碌时间只有一个区间。4.3 最实用的调试姿势把时间轴打印出来看限时模拟的心态崩溃点往往在于“不知道哪一步错了”。我的建议是尽早写一个辅助调试函数把整个时间桶以文字形式打印出来比如每一行显示08:00-09:00: 0人忙碌一眼就能看出哪里有意外。下面是一个简单的调试输出示例void debugPrint(int busy[]) { for (int t START; t END; t 15) { cout t / 60 : (t % 60 0 ? 00 : to_string(t % 60)) - busy[t] endl; } }把输出间隔设为 15 分钟只是为了快速浏览实际找 bug 时也可以逐分钟打印。有一次我就是靠这个才发现某个成员的忙碌区间被解析成了09:00到10:00但代码里存的是09:00到10:01因为在解析时多算了一个r-l1。发现问题后一行代码就修好了。4.4 输出前导零与字符串拼接的坑printf(%02d:%02d)是最稳妥的输出格式。有些人用cout输出时间时忘了补零导致09:00被输出成9:0这种格式错误在肉眼检查样例时容易被忽略但判题系统会直接给 Wrong Answer。如果使用cout可以借助setw(2)和setfill(0)控制宽度但每次输出后记得恢复填充字符否则会影响后续输出。我更推荐直接用printf简洁且不容易出错。5. 从这道题提炼出来的做题方法论限时模拟的上分策略5.1 读题的前 10 分钟应该做什么限时考试的节奏很关键。看到团队聚会这道题前 10 分钟不应该直接打开编辑器写代码。先把题目中的时间范围、时长下限、输出格式、特殊情况这几个参数圈出来再手动模拟一遍样例确认自己的理解和题目一致。重点验证的是边界条件。比如聚会时长刚好等于 h 小时是否合法如果满足时长的空闲窗口有两个应该选哪个这些判断直接影响后续编码浪费在前 10 分钟非常值得。以我个人的经验先花时间在草稿纸上画出时间轴把样例中的每个忙碌区间标出来再手动推导一遍预期输出比直接对拍代码更有效。这个习惯能让你在后 30 分钟写代码时分外安心因为每一步都清楚自己在干什么。5.2 构造边界用例外星人测试法不要只拿样例验证。自己构造几组极端数据比如所有人整天都很忙、所有人整天都有空、只有一段刚好凑够时长的窗口、多段窗口长度相等。这些用例能帮你提前暴露大多数边界问题。一种比较有效的测试法是“外星人测试”假装自己是判题程序专门想怎么刁难这段代码。比如成员忙碌时间精确到分钟要求聚会时长是 1 小时但所有空闲窗口都只有 59 分钟比如某个忙碌区间单人覆盖全天工作时间导致 No time比如忙碌区间出现在工作时间之外比如晚上 20:00 到 23:00这些时间不参与计算也不影响工作时间的空闲判断。我用 5.3 的小技巧总结一下边界用例的正确姿势是把时间桶长度表的边界值、最小值和最大值都覆盖到而不仅仅是构造几个看起来合理的正常输入。5.3 核心方法论时间区间问题的“差分/桶”模型团队聚会这道题背后是一个通用模型时间轴的区间覆盖计数。把每个区间对时间桶做增量标记最后统计满足条件的桶。这个方法适用于大量区间相关的问题比如会议室预订、在线用户数统计、共享单车租借时段统计。当你以后再遇到类似问题——给出一堆人对某资源段的占用区间求所有人可用的连续时间段——可以直接复用这套思维。甚至更进一步把“人数的忙碌计数”变成“资源被占用的计数”把“全员空闲”变成“计数为 0 或未占用”问题的套路几乎一样。从这个角度看团队聚会真正训练的并不是某个具体算法而是把一个实际场景抽象成数据结构的能力。而这个抽象能力比记住某个算法模板重要得多。6. 实际操作中的个人体会与避坑备忘录最后再分享几条实际操作中总结出来的经验。第一不要迷信所谓的“最优算法”。限时模拟考的是稳定输出不是炫技。如果我能用分钟桶快速解决就不会花时间写排序合并毕竟多写 50 行代码就多出 50 个可能出错的机会。第二输入全部读完后先调试解析结果再跑主要逻辑。很多时候队友能写出漂亮的时间轴扫描但错误却出在最开始的名字和字符串解析上。把每一步输入转换都打印出来能节省大量定位时间。第三善用草稿纸。在纸上画时间轴、标数字比盯着屏幕空想效率高得多。我每次遇到区间题都会先画一条横线在上面标出 480 和 1020 两个端点然后把每个忙碌区间用小括号标上去最后直接看图找连续空白段。这个过程和代码的运行逻辑几乎一一对应调试时非常有帮助。第四输出分支的优先级要明确。先判断是否满足时长再判断选哪段最后处理格式。如果不存在的场景下你还去访问最佳起始时间的数组下标轻则输出垃圾值重则数组越界崩溃。第五限时模拟的复盘比即时得分更重要。哪怕这一周只做了这么一道题把题目里的陷阱和你的调试过程整理成笔记下次遇到区间覆盖问题时你的第一反应就会从“有点慌”变成“这不就是团队聚会吗”。这种经验迁移才是这门课最珍贵的产出。按这套思路来做团队聚会这道题就不仅是一道限时模拟题而是一套可以复用的时间区间问题工具箱。动手敲一遍再自己构造几组怪数据踩踩坑你会有种“原来如此”的通透感。