PTA老板的作息表：时间区间补集与排序扫描解法-北京尧图网络

1. 拿到题先别写代码这份作息表本质是求时间轴的补集PTA 上这道《老板的作息表》我第一次看题面的时候扫了一眼就动手写了结果交了四发才过。原因很简单这道题的题干看起来像“格式化输出练习”实际上是一道包装在时间字符串外衣下的区间合并与补集问题。它要求你在一整天 00:00:00 到 23:59:59 的时间轴上把输入给出的若干段“已占用”的时间挖掉再把剩下的空档按时间顺序输出出来。输入是“老板什么时候在忙”输出是“老板什么时候空着”方向刚好是反的。这类题在 PTA 的 L1、L2 区间里出现频率不低难度标注往往不高但通过率经常不理想。因为这些题看着简单扣分点全藏在细节里时间要转成什么单位比较、区间首尾相接算不算空档、一天的结束点到底是 23:59:59 还是 24:00:00、输入行的分隔符空格数量不固定怎么办。每一个点单独拿出来都不难几个叠在一起就很容易让人在自测通过、提交 WAWrong Answer之间反复横跳。适合看这篇的人大概分三类正在刷 PTA 题库、被这道题卡住的同学想系统梳理“时间区间”这一大类题目的过题人以及带别人入门算法、需要一份能讲清楚“为什么这么写”的讲解材料的朋友。我下面会从题面结构、时间换算、扫描逻辑、代码实现、调试套路五个层面拆开讲而且每个关键选择我都会说清楚为什么这么做、不这么做会出什么事尽量让你看完之后遇到同类题能直接套思路而不是只能抄一段代码去交。提醒不同场次、不同题库版本里这道题的输出终点可能存在细微差异有的要求输出到 23:59:59有的覆盖到 24:00:00还有的会额外要求输出总时长。下面讲解以“半开区间覆盖到一天结束”这个最常见版本为主线具体边界请以你手上那份题面为准但方法完全通用。1.1 题面结构拆解输入是“已占用”要的是“未占用”把题干翻译成数据语言其实是这么一件事给若干个形如hh:mm:ss - hh:mm:ss的闭区间它们彼此不重叠题面通常会保证这一点但不一定保证有序它们共同覆盖了时间轴上的一部分位置。你需要找出时间轴上所有没有被覆盖的位置并且把这些位置按时间顺序合并成尽量少、尽量长的连续段最后每一段输出一行。这里的关键词是“合并成连续段”。如果输入是08:00:00 - 09:00:00和09:00:00 - 10:00:00那么这两段是首尾相接的中间没有留下任何空档你不应该输出09:00:00 - 09:00:00这种长度为零的鬼东西。很多人的第一版代码就栽在这儿——忘了判断“空档长度必须大于零”于是输出了大量零长度的区间。再往深想一层这道题真正要求你建立的心智模型是时间轴是一条从 0 开始、到某一点结束的一维直线输入给你的是若干条已经涂了颜色的线段你要输出所有没涂颜色的线段。建立这个模型之后剩下的事情就是把时间换算成可以比较和相减的数字然后做一次从左到右的清扫。跟字符串、跟日期、跟业务逻辑都没有关系。1.2 为什么纯字符串拼接一定会在边界翻车有人会想时间字符串格式固定字典序不就是时间序吗那我直接比较字符串行不行答案是——在“严格补零、格式统一”的前提下确实行08:30:00 09:00:00成立23:59:59 00:00:00也成立。这是定长补零带来的一个很舒服的性质很多老手也会顺手利用。但问题出在两个地方。第一你没法用字符串做出“两段时间相差多少”这种减法而这道题里恰恰需要判断空档长度是否为正、需要把当前覆盖到哪儿往前推。第二一旦输入里混进不补零的写法比如某个用例的时是9:05:03而不是09:05:03字典序立刻崩盘9:05:03会排在10:00:00后面因为字符9的编码大于1。你不可能在题面里找到“保证补零”的明确承诺所以这个假设一旦不成立就是整题崩。我的结论很直接别在这道题上炫技巧老老实实转成整数秒。整数天生可比较、可相减、可排序格式化问题留到最后一步再解决。看起来多写了几行实际上省掉了后面无数种诡异的边界情况。1.3 三个必须先确认的题面细节在动手之前我习惯先把三个细节在纸上写清楚否则写完还得返工。第一个是一天的起始和结束。绝大多数版本是从00:00:00开始结束点有两种写法23:59:59或者24:00:00。这两者的差别在于你怎么定义“覆盖”。如果用左闭右开区间[0, 86400)来描述一整天那么86400这个数就代表一天结束的那一刻输出的时候需要把它格式化成24:00:00或者特殊处理成23:59:59。如果题面明确要求最大到23:59:59那你就得把上界设成86399并且在最后一段用闭区间处理稍微麻烦一丁点。第二个是输入行里分隔符周围的空格。题面给的样例通常是08:00:00 - 09:00:00中间是“空格-短横-空格”。但真实用例里可能只有一个空格也可能有多个也可能没有。这时候如果你用getline读到一行再按固定位置切分只要少一个空格就全错。后面我会给一个用格式化输入自动吞掉空白的写法能省掉这一类麻烦。第三个是是否存在一整天都没有任何安排的情况。这种时候n可能是 0或者输入里只有一段覆盖全天的记录。前者的程序如果没处理空输入很容易在读入阶段就崩掉或者什么都不输出而正确答案应该是输出一整天。2. 时间与秒的互转整道题最容易被低估的一段这一层代码量最少但出问题的概率最高。我见过太多人主逻辑写得漂漂亮亮最后卡在%02d少写了一个 0或者s % 60和s % 3600用混输出变成8:0:0这种格式。时间换算的逻辑本身极其简单难的是把所有分支都覆盖到、把格式写到和题面一模一样。我通常把这一层单独封装成两个函数一个负责把时:分:秒解析成从零点开始的秒数一个负责把秒数格式化回字符串。封装的目的是让主逻辑里不出现任何*3600、/60这种魔法数字读代码的时候不会被这些常数打断思路。这个习惯在打比赛的时候尤其值钱因为时间紧主逻辑一乱就得重写。2.1 为什么我坚持统一转成秒用秒做内部表示有几个很实在的好处。第一比较和排序直接就是整数比较不用写任何自定义比较函数。第二区间的“长度”有了明确含义r - l大于零就代表有覆盖等于零就代表零长度逻辑上非常干净。第三区间的前后关系可以直接用、判断不需要知道具体是几点几分。还有一个容易被忽略的好处用秒做单位可以把“包含”和“相交”统一成一种处理。假设当前已经覆盖到cur秒新来一个区间[l, r)。如果l cur说明中间有空档输出[cur, l)然后cur max(cur, r)。这两行代码就同时处理了完全不相交、部分重叠、完全被包含三种情况不需要写三个if。这就是选对表示方式带来的红利。顺手算一下量级一天是 24 小时也就是 86400 秒。这个数量级用int完全够32 位有符号整数上限约 21 亿甚至用short都勉强能装下但没必要省这点空间。如果题目扩展到多天比如把日期也带上那就要换成更大的单位比如从某个纪元开始的秒数32 位整数在跨越几十年之后就会溢出那时候得用 64 位。这道题不用担心但心里有这个数遇到“跨天作息表”的变种题就不会翻车。2.2 解析函数里吞掉空格的写法C 里最省事的方式是用scanf或者cin配合格式串让输入函数自己跳过空白int h1, m1, s1, h2, m2, s2; scanf(%d:%d:%d - %d:%d:%d, h1, m1, s1, h2, m2, s2);格式串里%d前面的空格本身不严格要求匹配一个空格%d在读取整数之前会自动跳过任意数量的空白字符包括零个。也就是说-后面的空格数量对结果基本没有影响。这一点非常实用能挡掉“分隔符周围空格不固定”的一整类坑。如果你用cin注意cin h1读完之后流里还留着:直接cin m1会失败因为这个冒号不是数字。必须写成cin h1然后cin.ignore()吃掉冒号或者用scanf。这也是为什么我在这类题上基本不用cin 直接读时间太啰嗦。还有一种是getline读整行再手动切分思路是把行内所有非数字字符替换成空格再用stringstream逐个读数字。这种写法通用性最强能处理任何奇怪的分隔符但代码量和常数都更大。我一般在题目格式明确的时候用scanf格式含糊的时候才上stringstream。2.3 格式化输出的补零与终点值输出阶段最容易出两种错补零漏了以及终点值算错。补零的标准写法是%02d表示至少两位、不足两位用 0 填充。三个字段都用这个格式输出就一定是hh:mm:ss。千万别用%d再手动判断是否小于 10那种写法又长又容易漏分支。终点值的问题在于当你用半开区间[0, 86400)表示一整天的时候86400这个数字本身是“第二天的零点”并不属于今天。所以如果最后一段空档延伸到这一天结束你需要决定输出成什么。最稳妥的做法是看题面样例如果样例里出现过23:59:59那就把上界设成86399并且在最后一段用闭区间如果样例里出现的是24:00:00那就保持86400直接格式化。我的经验是大部分版本输出的是23:59:59但样例里没出现过的边界千万不要靠猜宁可自己造一个“一整天全空”的用例看看题目期望什么。string fmt(int sec) { char buf[16]; int h sec / 3600; int m sec % 3600 / 60; int s sec % 60; snprintf(buf, sizeof(buf), %02d:%02d:%02d, h, m, s); return string(buf); }这段代码我几乎是背下来的因为它在这类题里会重复出现无数次。注意sec % 3600 / 60这个写法先取余再除等价于“去掉小时之后剩下的秒数里有多少个整分钟”比(sec / 60) % 60少一次除法也更直观一点。3. 排序后再扫一遍把散乱区间缝成一条覆盖线主逻辑部分其实只有十几行但每一行都有它的理由。我见过很多人写法上是“对每个区间去找它前面的所有区间看看有没有重叠”写出来是双重循环逻辑复杂还容易漏情况。正确的思路是先把区间按起点排序然后从左往右单向扫一遍维护一个“目前已经覆盖到哪儿”的指针。这样每个区间只看一次代码短、思路清晰、不会漏。这个套路不只是这道题能用。合并区间、会议室安排、区间覆盖问题、日程冲突检测本质都是同一件事。把这套“排序单指针推进”的模板吃透后面遇到一堆同类题都能直接套。我在带别人过题的时候一般会让他们先把这套模板手写三遍写到不看笔记也能一次写对为止。3.1 输入顺序不可信时的处理题目给样例的时候输入通常是有序的这会给人一个错觉好像不用排序。但题面里绝大多数情况下不会承诺输入有序而且很多题目的隐藏用例就是专门拿乱序输入来卡人的。我就吃过这个亏本地测了三组样例全过提交直接 WA把输入打出来一看最后一行的时间比第一行还早。所以排序这一步不能省。C 里vectorpairint,int默认的sort就是按pair的字典序比较先比第一个元素再比第二个而这正好就是“按起点升序、起点相同按终点升序”完全符合需要。也就是说你根本不用自己写比较函数sort(segs.begin(), segs.end())一行就够了。如果用的是结构体或者自定义类型那就得写一个operator或者传一个 lambda。我一般选 lambda写起来短sort(segs.begin(), segs.end(), [](const pairint,int a, const pairint,int b) { return a.first b.first; });这里只按起点排就够了终点顺序无所谓因为后面用max处理。不过按pair默认排序也不会有任何副作用所以我不太纠结这个细节。3.2 用“当前覆盖到的位置”做单向推进核心变量只有一个cur表示“从零点开始我已经确认被覆盖到第几秒”。初始值是 0因为它前面没有任何东西所有位置都还空着。然后遍历排序后的每个区间[l, r)如果l cur说明从cur到l这一段没有被任何区间覆盖输出它然后把cur推到r。如果l cur说明这个区间和已经覆盖的部分接上了或者被包住了不产生任何输出只需要把cur推到max(cur, r)。遍历完之后如果cur还没到一天结束说明尾巴上还有一段空档单独输出。这个逻辑的正确性可以用一个不变式来描述每轮循环结束时[0, cur)中的所有位置都已经被处理过要么被覆盖、要么已经被作为空档输出。初始时cur 0[0, 0)是空集成立。每一步要么扩展cur要么在扩展之前把中间那段吐出去不变式保持。循环结束后剩下的[cur, 86400)就是最后一段空档。写代码的时候把这个不变式在脑子里过一遍比事后对着错误输出瞎猜有用得多。3.3 相交、包含、首尾相接的实际走向光看公式容易晕我拿几组具体数据走一遍你就明白为什么max是关键了。情况已有覆盖新区间输出新 cur说明完全不相交[0, 100)[200, 300)[100, 200)300中间空档被吐出首尾相接[0, 100)[100, 200)无200l 等于 cur不产生零长度段部分重叠[0, 150)[100, 200)无200l 小于 cur直接推进完全被包含[0, 300)[100, 200)无300max 保住 300 不被缩回 200完全包含旧的[0, 100)[50, 400)无400max 取到 400这张表里最值得盯的是“完全被包含”那一行。如果代码里写成cur r而不是cur max(cur, r)遇到一个完全被包住的区间cur就会从 300 缩回 200后面本来应该被覆盖的[200, 300)就会被误判成空档输出答案直接错。这个错误特别隐蔽因为样例数据里往往没有“被包含”的情况本地测不出来。“首尾相接”那一行也是重点。因为用了半开区间l cur时l cur不成立什么都不会输出。如果你用的是闭区间表示这里就得额外判断l cur 1才行稍不注意就会输出一段xx:xx:xx - xx:xx:xx前后完全相同的垃圾数据。这就是我前面说“半开区间更省心”的实际理由。4. 完整实现与两种解法对照布尔打点法和排序扫描法到这儿思路已经清楚了可以上代码。我给两份一份是排序扫描的正解另一份是拿来做对拍基准的布尔打点法。很多人会觉得暴力法“不优雅”所以不屑于写但在这道题上暴力的那份反而是我调试时最依赖的工具因为它足够笨、足够直白出错的可能性极低可以拿它当标准答案来验证正解。顺便说一句这道题的时间范围固定是 86400 秒布尔数组的规模非常小其实暴力法本身就能 AC而且写起来更快、更不容易错。我在真正比赛的时候会怎么选如果时间紧张、只求过题我直接写布尔打点法如果这道题后面还有变种比如时间范围变成任意大、或者要处理多天那就得上排序扫描。两种都得会选哪个看场景。4.1 一份可以直接提交的主流程代码#include bits/stdc.h using namespace std; int toSec(int h, int m, int s) { return h * 3600 m * 60 s; } string fmt(int sec) { char buf[16]; snprintf(buf, sizeof(buf), %02d:%02d:%02d, sec / 3600, sec % 3600 / 60, sec % 60); return string(buf); } int main() { int n; if (scanf(%d, n) ! 1) return 0; vectorpairint,int segs; segs.reserve(n); for (int i 0; i n; i) { int h1, m1, s1, h2, m2, s2; scanf(%d:%d:%d - %d:%d:%d, h1, m1, s1, h2, m2, s2); int l toSec(h1, m1, s1); int r toSec(h2, m2, s2); if (l r) segs.push_back({l, r}); // 防御跳过零长度或倒序的脏数据 } sort(segs.begin(), segs.end()); const int DAY 86400; int cur 0; for (auto p : segs) { int l p.first, r p.second; if (l cur) { printf(%s - %s\n, fmt(cur).c_str(), fmt(l).c_str()); } cur max(cur, r); } if (cur DAY) { printf(%s - %s\n, fmt(cur).c_str(), fmt(DAY).c_str()); } return 0; }几个细节值得单独拎出来说。segs.reserve(n)不是必须的但养成习惯挺好尤其是n可能到十万级别的时候避免频繁扩容。这道题n一般不大但写代码的时候不差这一行。if (l r)这个防御判断是我被脏数据伤过之后加的。规范题面不会给零长度或者终点早于起点的区间但万一呢零长度区间其实无害l cur时不产生输出cur max也不会变但倒序区间会让max逻辑变乱。加一行判断成本几乎为零。fmt(DAY)在DAY 86400的时候会输出24:00:00。如果你的题面要求终点显示为23:59:59那就在这里做特殊处理或者干脆把DAY改成86399并且把最后一段的右端点用闭区间解释。这个点必须对着样例确认别猜。printf配%s和c_str()比cout快不少PTA 上有些题的输入量不小养成用printf的习惯没坏处。4.2 布尔打点法拿来做对拍基准最省事#include bits/stdc.h using namespace std; int toSec(int h, int m, int s) { return h * 3600 m * 60 s; } string fmt(int sec) { char buf[16]; snprintf(buf, sizeof(buf), %02d:%02d:%02d, sec / 3600, sec % 3600 / 60, sec % 60); return string(buf); } int main() { int n; scanf(%d, n); static bool busy[86400]; for (int i 0; i n; i) { int h1, m1, s1, h2, m2, s2; scanf(%d:%d:%d - %d:%d:%d, h1, m1, s1, h2, m2, s2); int l toSec(h1, m1, s1), r toSec(h2, m2, s2); for (int t l; t r; t) busy[t] true; } int i 0; while (i 86400) { if (busy[i]) { i; continue; } int j i; while (j 86400 !busy[j]) j; printf(%s - %s\n, fmt(i).c_str(), fmt(j).c_str()); i j; } return 0; }这段代码的思路简单到不需要解释把每一秒打上标记然后扫一遍找连续的空白。它的正确性几乎是“显然”的这正是它作为对拍基准的价值所在。当你正解和它输出不一致的时候可以百分之百确定是正解错了而不用怀疑基准本身。当然它也有代价如果题目把时间范围扩大到多天或者时间精度到毫秒数组就开不下了。所以它适合用来验证不适合当作唯一方案。4.3 两种解法的取舍与复杂度对照维度布尔打点法排序扫描法时间复杂度O(n 86400)O(n log n)空间复杂度O(86400) 固定O(n)代码行数约 25 行约 35 行出错概率低几乎没有边界中max和边界易错时间范围扩展性差范围一大就开不下好任意范围都能处理适合场景定点范围、赶时间、做对拍通用解法、需要扩展的变种从表里能看出来这道题上两者的差距其实很小86400 的常数在现在的机器上根本不叫事。真正拉开差距的是扩展性如果这道题后面跟着一个“老板的作息表加强版”时间范围变成从某年某月某日到某年某月某日那布尔打点法直接废掉排序扫描法一行不用改只要把时间单位换一下。所以我的建议是学会排序扫描法作为主力布尔打点法作为验证工具两个都别丢。5. 提交前我必定检查的几项与调试套路代码写完、样例过了其实只是走了半程。这道题的坑大部分在样例覆盖不到的地方所以提交前的自查和提交后的调试才是真正决定能不能一次过的环节。我在被这类题反复教育之后慢慢总结出一套固定的检查流程现在基本能做到写完先自查、再提交很少出现反复 WA 的情况。这套流程的核心思路是不要指望样例帮你发现边界问题样例永远只覆盖最正常的情况。你得主动去构造那些“看起来很怪但完全合法”的输入让程序在你自己手里先崩一次而不是在判题机那里崩。5.1 我遇到的几次典型错法定位过程第一次 WA是因为没排序。样例的输入恰好是有序的所以我本地怎么测都对。定位方法很简单把读入的区间在排序前后各打一遍一眼就看出顺序是乱的。第二次 WA是cur r写成了cur max(cur, r)的反面。这次更阴险因为我造的测试数据里区间都是递增的没有包含关系。后来我专门加了一组[00:00:00 - 12:00:00]和[02:00:00 - 03:00:00]输出立刻多出一段03:00:00 - 12:00:00问题暴露。第三次 WA是输出终点。我写的是86400格式化出来是24:00:00但题面期望23:59:59。这个只能靠仔细读样例代码逻辑完全没错纯粹是“理解题面”的问题。第四次n 0的时候程序什么都不输出正确答案是输出一整天的空档。原因是我把主循环写在了if (n 0)里面纯属手滑。这四次的共同点是本地全过提交才炸。所以我现在的习惯是样例跑完之后立刻手工构造一组“极端输入”再跑一遍具体造什么下面这张表就是我的清单。5.2 造数据和对拍的具体操作我常用的测试数据构造思路按优先级排空输入n 0期望输出一整天的空档或者按题面要求的那一段。完全覆盖一段00:00:00 - 24:00:00如果题面允许期望什么都不输出。包含关系一个大区间套一个小相处验证max逻辑。首尾相接08:00:00 - 09:00:00和09:00:00 - 10:00:00验证不输出零长度段。乱序输入把正常数据打乱顺序喂进去验证排序。一天两头00:00:00 - 00:00:01和23:59:58 - 23:59:59验证首尾边界不超过范围。对拍的话我用一份 Python 脚本随机生成合法输入然后让两个程序分别跑比对输出。生成逻辑很简单随机切几个点构造若干互不重叠的区间确保不越界。跑个几百轮基本能把隐藏的边界问题全揪出来。如果两个程序输出不一致把那份输入留下来单独分析比盯着代码看快十倍。一个实际的小技巧把输出重定向到文件再 diff比在终端里滚屏肉眼比对靠谱得多。命令行里./a in.txt out1.txtpython b.py in.txt out2.txt然后diff out1.txt out2.txt差异一目了然。5.3 提交前的自检表检查项具体做法踩坑后果是否排序看代码里有没有sort乱序输入直接错是否用max推进看cur的更新语句被包含区间导致多输出零长度段是否过滤l cur而不是l cur输出xx - xx的无效行格式化是否补零三个字段都用%02d输出8:0:0格式不符终点值是否正确对比样例里的最大时间24:00:00与23:59:59之争n 0是否处理手造一组空输入跑一遍该输出时不输出是否有未初始化变量编译加-Wall看警告随机性错误极难复现输入是否吞掉空格用scanf格式串而非定长切分分隔符多空格时解析失败这张表我现在基本是条件反射地过一遍前后不超过两分钟但省下来的重交次数远不止两分钟。最后分享一个小经验这道题做完之后别急着关掉。把代码里的DAY改成一个参数试试“如果一天不是 24 小时而是任意长度”会怎样你会发现排序扫描法几乎不用改而布尔打点法立刻需要重新设计。这种“改一个条件看方案还成不成立”的练习比单纯刷十道同类题更能建立起对区间问题的直觉。我自己就是靠这种折腾慢慢把一类题的解法从“背下来”变成了“想得起来”。

PTA老板的作息表：时间区间补集与排序扫描解法

相关推荐

AI代理与智能爬虫技术趋势及实战解析

电子遗嘱活体验证V步骤1：Python构建司法级身份证据链

多智能体协同优化：冲突解决与性能提升实践

更多资讯

多模态高层融合技术与Transformer在机器人感知中的应用

Gemini 4 Argon 1M输出窗口：长程Agent工程边界与架构实践

多模态高层融合技术解析与应用实践

31岁晋升小米22级：职场跃迁的底层逻辑与实操指南

2024年AI岗位需求激增与零基础转型实战指南

Python大数据处理实战：从Pandas到PySpark核心技巧

今日更新

基于YOLOv11的石油泄漏智能检测系统开发实践

AI行业变局：合规、Mod化与上下文管理的实战启示

计算机视觉与AI原生应用融合的技术实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？