说实话打开“团队聚会”这道限时大模拟题的那一刻我是有点懵的。题面里密密麻麻全是类似“2020-01-01 08:00”的时间字符串每个人后面跟着好几个时间段最后还要你输出一个具体的“某年某月某日某时某分”看起来就像一道字符串处理地狱题。但等你把数据读进去把每个时间都转成整数分钟之后会发现这道题的内核其实极其朴素区间合并然后求补集最后在空闲区间里找一个最长候选段。这篇文章我会按自己拿到的题面来拆解这道题把时间转换、区间合并、边界处理、输出格式这些容易扣分的点全部过一遍最后给出可以直接交作业的C代码。不管题目细节怎么变核心思路都能复用。适合正在写这道作业题的同学也适合想复习“区间合并 时间离散化”这类模型的算法学习者。1. 题目场景还原团队聚会到底在考什么1.1 实际题面长什么样题面大致讲的是某团队想找一段时间聚会。团队里的每个人都会给出一份“忙碌时间段”列表每个忙碌时间段由两个“YYYY-MM-DD HH:MM”格式的时间点描述意思是从前一个时间点到后一个时间点之间这位成员没空。现在要找一个连续时间段让团队里所有成员都有空并且这个时间段的长度不能短于给定的聚会时长T。如果存在多个满足条件的时间段一般按“持续时间最长优先持续时间相同则开始时间最早优先”来选。如果根本找不到就输出一段提示文字。这里有个很容易被忽略的细节题面里的“聚会时长”可能以分钟为单位也可能以小时为单位而忙碌时间段天然精确到分钟。不管单位是什么第一步都建议把一切都换算成分钟后面比较时才不会出现一小时等于六十分钟这种低级换算错误。1.2 我按这个输入输出格式准备我拿到的版本是多组输入读到文件尾结束。每组数据的第一行是一个整数T表示聚会至少需要持续多少分钟第二行是整数m表示团队人数接下来有m行每行第一个整数n表示这个人的忙碌时间段数量后面跟着2n个时间字符串每两个字符串构成一个忙碌时间段。输出时每个测试点先输出一行“Scenario #k:”k从1开始编号。如果找到了满足条件的空闲时间段就输出类似“2020-01-03 18:00 to 2020-01-03 21:00”这样的形式如果找不到输出“No such time slot.”。每组数据之间要求空一行。这里要强调一点不同学校的题面细节可能有出入比如有人拿到的版本是先给m再给T或者团体人数中还包括“队长”这种角色但其实都不影响核心算法。你只需要把输入顺序和最后输出的字段名按自己手里的题面调整一下即可。1.3 为什么限时模拟热衷出这种题第十周的限时大模拟本质上不是考冷门算法而是考三件事。第一是抽象能力能不能从一段自然语言描述里看出来这本质上是“区间求交”问题。第二是数据清洗能力一堆“2020-01-01 08:00”这样的字符串能不能稳定地转成可计算的整数并且在输出的时候再还原回去。第三是容错能力多组输入、空行、前导零、闰年、区间端点开闭这些都是真实业务里最容易出bug的地方。实际工程里会议室预订、多人日程协调、客服排班冲突检测做的都是同一件事把人的空闲时间看成若干线段然后求一个满足条件的公共交集。所以这道题不是单纯的刷题玩具课程组在第十周安排它就是想逼你在限时压力下把这类“日程协调”问题做到条件反射。2. 核心思路拆解把日程表变成区间集合2.1 别按分钟去枚举先想清楚区间模型我看到这个题的第一反应其实不是“区间合并”而是“枚举每一分钟”因为“所有成员都有空”这句话太像“查询某个时刻是否空闲”了。但仔细一算就发现不行如果时间范围是一整年分钟数是52万多再乘上人数和区间数量直接枚举的常数很大更麻烦的是输出答案时要找到“一段连续时间”的起止时刻枚举单点之后还要把相邻空闲分钟拼起来这个拼接过程照样要处理开闭边界。正确的模型是把每个人的每个忙碌时间段看成一条线段所有忙碌线段的并集就是“团队里至少一个人没空”的全部时间。那么总时间范围减去这个忙碌并集剩下的就是所有成员都有空的候选空闲区间。最后只需要在这些空闲区间里挑一个长度不少于T、并且最长或最早开始的即可。换句话说这道题的高层解法只有两步先求“所有人忙碌区间的并集”再求这个并集相对于总时间范围的补集。这两步都可以用排序加线性扫描完成。2.2 左闭右开约定解决边界问题的最省心方式区间题最烦的就是“某个时刻到底算不算空闲”。如果你拿到的题面说忙碌区间是“[开始, 结束]”那结束时刻本身也是忙碌的空闲区间就要从“结束时刻1分钟”开始算如果忙碌区间表示“到结束时刻为止”那结束时刻又变成了空闲的开端。这种一字之差就能让WA和AC差出一个提交。我的建议是无论题面怎么写在内部实现时把所有区间统一成左闭右开[l, r)表示从l分钟开始到r分钟结束l时刻处于区间内r时刻已经离开区间。区间长度直接用r - l计算不需要加一减一也不会产生“到底哪一分钟属于空闲”的语义纠纷。在这个约定下合并忙碌区间时当前合并区间为[curL, curR)遇到新区间[l, r)时判断条件应该是l curR才说明中间有空隙需要把当前区间保存并开一个新区间如果l curR说明两个区间重叠或刚好首尾相接此时只需要把curR更新成max(curR, r)。注意等于号的情况很重要l curR时两个忙碌区间中间没有空闲时间一旦拆开就会出现长度为零的伪空闲区间后面选答案时很容易出问题。2.3 求空闲区间的完整流程确定总时间范围是个隐藏考点。题目说时间范围是“这一年从第一天到第二天”但实现时必须考虑如果要覆盖到12月31日23:59这一分钟总范围右端点应该是下一年的1月1日00:00。我直接用两个常量ALL_START 2020-01-01 00:00 ALL_END 2021-01-01 00:00这两个时间都转成分钟数后整个是左闭右开区间[ALL_START, ALL_END)。这样2020年12月31日23:59到24:00这一分钟才不会被丢掉。求空闲区间的扫描流程是用一个变量cur表示当前还没被任何忙碌区间覆盖的位置初始为ALL_START。按左端点顺序遍历合并后的忙碌区间如果cur 当前忙碌区间的l说明[cur, l)是一段空闲时间保存下来。然后cur更新为max(cur, 当前忙碌区间的r)。全部遍历完后如果cur ALL_END说明最后还有一段空闲时间保存[cur, ALL_END)。这个过程非常像“扫地”cur始终指向已经扫过的位置的右边界遇到一个忙碌区间就判断前面有没有没扫到的地方然后继续往前推。2.4 差分数组方案为什么被我放弃我知道不少人会想到差分数组把每个忙碌区间[l, r)拆成diff[l]和diff[r]--然后求前缀和前缀和为0的位置就是所有人都空闲的位置。理论上这个方案也能做但实际写起来陷阱很多。第一一年有52万多分钟如果连续给好几组数据每组都开一个52万长度的数组重置成本不能忽略。第二输出时需要把“前缀和为0的连续段”拼出来仍然要处理离散和连续的关系。第三如果时间范围跨了多年数组长度还要继续放大思维负担更重。相比之下“排序 合并 补集”的做法只跟区间数量相关数据量再大也不会被年份拉爆。而且判断逻辑非常直观写错了也容易通过小样例定位。限时环境下我追求的是“短时间写对而不是炫技”。3. 时间转换与输出格式化全题的隐蔽得分点3.1 数字格式化读取比字符串处理更稳最开始的版本里我用字符串读入再把每个字符串拆成年月日时分。后来发现有更省事的方式直接用scanf按格式读取数字。时间字符串的标准格式是“YYYY-MM-DD HH:MM”也就是说两个时间串连在一起可以写成2020-01-01 08:00 2020-01-01 12:00scanf天然按空白符分割但“2020-01-01”和“08:00”之间还有空格所以不能靠%s一次读进一个完整时间串。更稳的做法是直接读取六个整数int y1, mo1, d1, h1, mi1; scanf(%d-%d-%d %d:%d, y1, mo1, d1, h1, mi1);scanf会跳过空白然后按格式匹配数字和分隔符。只要输入格式正确这个办法可以一次把完整时间点解析成五个整数。两个时间点之间再读一遍即可。这个技巧看似简单但能帮你省掉很多字符串处理代码。限时赛里少一行代码就少一个出错机会。3.2 闰年和跨年toMinutes的完整实现为了把时间点转成分钟数需要算出这个时间点距离基准时间“2020-01-01 00:00”过了多少分钟。实现时先累加从基准年到目标年份之间每一年的总天数再累加当年目标月份之前的天数最后把目标日减一乘以1440后加上小时和分钟。这里必须处理闰年能被400整除或者能被4整除但不能被100整除的年份是闰年闰年的2月有29天。如果实现时偷懒只对2020年特判一旦测试数据里出现2021年这种普通年份就会在2月之后的所有日期上错一天。更稳的做法是写一个函数判断任意年份。当年份跨年时比如从2020-12-31 23:00到2021-01-01 01:00只要toMinutes函数能正确处理2021年区间长度自然就是120分钟不需要额外讨论。3.3 逆转换把分钟数还原成时间字符串选出答案区间后手里拿到的是两个分钟数ans.l和ans.r还需要把它们格式化成“YYYY-MM-DD HH:MM”输出。逆转换的思路是先用days minutes / 1440算出从基准年1月1日起经过了多少整天用rem minutes % 1440算出当天已经过了多少分钟。然后从基准年开始如果days大于等于这一年的总天数就减去这一年的天数并把年份加一直到days小于当前年份的总天数。接着从1月开始逐月尝试如果days大于等于当前月份天数就减掉它并推进月份否则就停在这个月。最后d days 1就是具体日期h rem / 60mi rem % 60。这段逻辑不复杂但很考细心。输出时用sprintf拼字符串格式化占位符用“%02d”保证月份、日期、小时、分钟都有前导零。年份用“%04d”防止年份小于1000时输出4位以下数字。3.4 输出里的三个“必须”第一时间字符串里必须有空格比如“2020-01-01 08:00”中间那个空格经常被复制路径上的同学漏掉。第二连接词“to”两边都有空格输出样例是“2020-01-01 08:00 to 2020-01-01 10:00”少了空格会被判格式错误。第三每组case之间要输出一个空行但第一组之前不能有额外空行最后一组之后一般也不要多余空行。实现时我用一个kase计数器在kase大于1时先输出一个换行符再输出“Scenario #k:”。这些细节单独看都很小但加起来就决定了你是AC还是PE。限时模拟里时间非常宝贵养成把输出逻辑封装成一个函数、集中检查的习惯会省不少调试时间。4. 完整C实现与逐段注释4.1 数据结构、排序和合并我用一个Interval结构体保存区间的左端点和右端点两个成员都是long long类型。排序时直接按左端点升序左端点相同按右端点升序。因为数据量不大这种朴素排序完全够用。合并的过程很简单遍历排序后的忙碌区间如果当前结果列表为空或者当前区间的左端点大于结果列表最后一个区间的右端点就把它作为新区间加入否则把最后一个区间的右端点更新为两者中更大的那个。这个合并逻辑的关键点就是那个大于号而不是大于等于号原因在2.2里已经说过。4.2 主流程读入、算空闲、选答案主流程里先读T再读m。对于每个人读入n后依次读2n个时间点。每个忙碌时间段用两个完整时间点组成调用toMinutes得到左右端点存入busy数组。之后按照前面说的步骤排序、合并、求空闲区间。最后遍历空闲区间用变量has标记是否已经找到答案再用len表示当前空闲区间长度。当len T且区间非空即区间左端点小于右端点时进入答案更新逻辑如果还没有答案直接记录否则比较长度长度更长就替换长度相等时比较左端点左端点更早也替换。需要说明的是我的输入版本先读T再读m。如果你手里的版本顺序不同只要把读取顺序对调即可算法部分完全不用动。4.3 可直接提交的完整代码下面是完整实现C17编译通过。#include cstdio #include vector #include algorithm using namespace std; struct Interval { long long l, r; Interval(long long _l 0, long long _r 0) : l(_l), r(_r) {} bool operator (const Interval other) const { if (l ! other.l) return l other.l; return r other.r; } }; int monthDays[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; bool isLeap(int y) { return (y % 400 0) || (y % 4 0 y % 100 ! 0); } int getYearDays(int y) { return isLeap(y) ? 366 : 365; } long long toMinutes(int y, int mo, int d, int h, int mi) { long long days 0; // 基准年固定为2020题目时间范围一般就是2020自然年 for (int i 2020; i y; i) days getYearDays(i); for (int i 1; i mo; i) { if (i 2 isLeap(y)) days 29; else days monthDays[i]; } days (d - 1); return days * 1440 h * 60 mi; } void fromMinutes(long long minute, char out[]) { int y 2020; long long days minute / 1440; int rem (int)(minute % 1440); while (days getYearDays(y)) { days - getYearDays(y); y; } int mo 1; while (true) { int md (mo 2 isLeap(y)) ? 29 : monthDays[mo]; if (days md) break; days - md; mo; } int d (int)days 1; int h rem / 60; int mi rem % 60; sprintf(out, %d-%02d-%02d %02d:%02d, y, mo, d, h, mi); } int main() { int T; int kase 0; while (scanf(%d, T) ! EOF) { kase; int m; scanf(%d, m); vectorInterval busy; for (int i 0; i m; i) { int n; scanf(%d, n); for (int j 0; j n; j) { int y1, mo1, d1, h1, mi1; int y2, mo2, d2, h2, mi2; scanf(%d-%d-%d %d:%d %d-%d-%d %d:%d, y1, mo1, d1, h1, mi1, y2, mo2, d2, h2, mi2); long long l toMinutes(y1, mo1, d1, h1, mi1); long long r toMinutes(y2, mo2, d2, h2, mi2); if (l r) busy.push_back(Interval(l, r)); } } long long ALL_START toMinutes(2020, 1, 1, 0, 0); long long ALL_END toMinutes(2021, 1, 1, 0, 0); sort(busy.begin(), busy.end()); vectorInterval merged; for (size_t i 0; i busy.size(); i) { if (merged.empty() || busy[i].l merged.back().r) { merged.push_back(busy[i]); } else { if (busy[i].r merged.back().r) { merged.back().r busy[i].r; } } } vectorInterval free; long long cur ALL_START; for (size_t i 0; i merged.size(); i) { if (cur merged[i].l) { free.push_back(Interval(cur, merged[i].l)); } if (merged[i].r cur) { cur merged[i].r; } } if (cur ALL_END) { free.push_back(Interval(cur, ALL_END)); } bool has false; Interval ans; for (size_t i 0; i free.size(); i) { long long len free[i].r - free[i].l; if (len T free[i].l free[i].r) { if (!has || len ans.r - ans.l || (len ans.r - ans.l free[i].l ans.l)) { ans free[i]; has true; } } } if (kase 1) printf(\n); printf(Scenario #%d:\n, kase); if (!has) { printf(No such time slot.\n); } else { char s1[20], s2[20]; fromMinutes(ans.l, s1); fromMinutes(ans.r, s2); printf(%s to %s\n, s1, s2); } } return 0; }代码不长但每一段都有实际作用。最关键的三行判断是合并区间的大于号、求空闲区间时cur的更新逻辑以及选答案时对“长度相等选更早开始”的处理。这三处也是我实际提交里翻过车的地方。5. 限时模拟里的三次WA我的踩坑复盘5.1 总范围右端点ALL_END少定义了1分钟我第一次写的总结束时间是“2020-12-31 23:59”。从直觉上看这已经是12月31日最后一分钟了应该没错。但在左闭右开区间模型里[2020-01-01 00:00, 2020-12-31 23:59)实际上不包含23:59这个时刻本身因为右端点是不被包含的。也就是说我在还没开始计算之前就把2020年最后一分钟丢掉了。如果恰好有人在那最后59分钟里有空答案就会少算一段。当时的问题是样例恰好避开了最后一天导致我在本地怎么跑都对交上去就是WA。这个坑的教训是处理“到某一年最后一天”的时间范围时右端点永远设成下一年的1月1日00:00。用左闭右开去理解你会发现这才是能覆盖完整一年时间的唯一干净写法。5.2 相邻忙碌区间被分开等于号引发的伪空闲段合并区间时我第一次写的条件是if (merged.empty() || busy[i].l merged.back().r)注意这里用了大于等于号。在左闭右开语义下两个忙碌区间[1, 3)和[3, 5)刚好首尾相接中间没有任何空闲时间。但按照这个条件它们会被当成两个独立区间保存于是后续求空闲区间时会在3这个位置产出一个长度为0的伪空闲段[cur3, l3)。这个伪空闲段的长度是0正常情况下不会被选为答案因为题目要求聚会时长T为正数。但如果我们自己写测试用例时用了T0去验证边界它就会被打印成“2020-01-01 03:00 to 2020-01-01 03:00”这种诡异输出。虽然标准数据不一定包含T0但这类边界数据能暴露模型是否干净。修正方式就是我把大于等于改成严格大于号只有l curR时才开始新区间。这样等于号归入“可合并”的范畴忙碌区间仍然保持连续。5.3 空行、大小写、句号格式分不是白送的还有一次WA纯粹是格式问题。题目要求每组case之间输出一个空行我用printf(\n)写在了每组case输出的开头但这样会在第一组之前也产生一个空行和题面要求不符。正确做法是维护一个kase变量从第二组开始、每一组输出之前先补一个空行。另外输出“No such time slot.”时结尾的句号很容易漏。还有“Scenario #%d:”这个冒号它后面没有空格但我一开始手滑加了一个空格导致和期望输出不一致。这些都是零成本能避免的错误但限时状态下人一紧张就特别容易犯。我的经验是把输出格式的全部细节列成清单写在代码注释的最前面。每次提交前对着清单逐项检查一遍比依赖肉眼扫屏要靠谱得多。5.4 提交前的自查清单最后分享一套自己常用的自测用例每次写完这类题都会跑一遍确认没问题再提交。只有一个人而且全天有空应该输出从“2020-01-01 00:00”到“2021-01-01 00:00”的完整空闲段前提是聚会时长不超过全年分钟数。只有一个人全天忙碌应该输出“No such time slot.”。两个人的忙碌区间完全错开应该没有任何公共空闲时间输出提示。有两个忙碌区间刚好首尾相接不应产生长度为零的伪空闲段。某一个空闲段的长度恰好等于T这个边界值必须被选中。T0时程序不应输出长度为0的时间段。聚会时间跨年比如从“2020-12-31 23:00”到“2021-01-01 01:00”检查toMinutes和fromMinutes是否都能正确处理。每次提交前把这几个用例跑一遍能过滤掉绝大多数的边界错误。限时模拟考的就是“你能不能在同一道题里避开这些坑”而不是“你会不会更高级的算法”。这套题做完之后我把时间转换的两个函数存成了自己的模板后面凡遇到时间区间题直接粘贴。限时大模拟最考验的就是这种“可复用的代码资产”。另外不要迷信题面里那种“从1月1日到12月31日”的说法算法模型上用开区间就能少掉一大堆边界麻烦。最后提醒一句团队聚会这种题只要你把区间模型建得干净写代码的时间不会超过30分钟真正吃掉时间的是你反反复复纠结“这里到底要不要加1”的内心戏。想明白了这道题就是区间合并的熟练度测试而已。