PTA天梯赛L2-042题保姆级攻略：用C++ STL vector和sort轻松找出老板作息表的‘摸鱼’时间

PTA天梯赛L2-042题解：用侦探思维破解老板的"摸鱼"时间

最近在PTA天梯赛的题库中，有一道关于时间区间处理的题目引起了我的注意。题目描述了一位老板在网上晒出自己的作息时间表，却被眼尖的网友发现存在时间空白。这让我想起了一个有趣的比喻：我们就像数字侦探，要从看似完整的时间表中找出那些被刻意隐藏的"摸鱼"时刻。

这道题编号L2-042，考察的核心是如何处理不连续的时间区间并找出其中的空白。对于准备算法竞赛的同学来说，这不仅是练习STL使用的绝佳机会，更是培养问题分解能力的典型案例。下面我将从解题思路、代码实现到优化技巧，带你一步步揭开这道题的神秘面纱。

1. 问题分析与建模

首先，我们需要明确题目的具体要求。给定N个时间段，每个时间段格式为"hh:mm:ss - hh:mm:ss"，要求找出一天中未被这些时间段覆盖的所有区间。这些区间需要按时间顺序输出，且题目保证输入的时间段不会重叠。

关键观察点：

• 所有时间都在00:00:00到23:59:59之间
• 输入区间按任意顺序给出
• 相邻区间可能有端点重合（如A区间结束于08:00:00，B区间开始于08:00:00）
• 需要检查三个边界：开始前、中间间隙、结束后

我们可以将这个问题建模为在时间线上寻找"空隙"的过程。想象一条从00:00:00到23:59:59的时间轴，上面已经标记了一些线段（输入的时间段），我们的任务是找出所有未被线段覆盖的部分。

2. 解题思路与算法设计

解决这个问题的关键在于如何高效地处理时间区间并找出间隙。以下是详细的思考过程：

2.1 输入处理与存储

首先需要将输入的时间段存储起来。由于题目中的时间都是字符串格式，我们可以直接使用vector<string>来保存原始输入。但更高效的做法是将时间转换为秒数，方便比较和排序。

struct Time { int h, m, s; int toSeconds() const { return h * 3600 + m * 60 + s; } }; vector<pair<Time, Time>> timeIntervals;

2.2 时间区间排序

未排序的时间区间难以处理，我们需要先按开始时间进行排序：

bool compareIntervals(const pair<Time, Time>& a, const pair<Time, Time>& b) { return a.first.toSeconds() < b.first.toSeconds(); } sort(timeIntervals.begin(), timeIntervals.end(), compareIntervals);

2.3 寻找间隙的算法

排序后，我们可以按顺序检查相邻区间之间的间隙：

1. 检查第一个区间是否从00:00:00开始
2. 检查相邻两个区间之间是否有间隙
3. 检查最后一个区间是否到23:59:59结束

算法伪代码：

if 第一个区间的开始 > 00:00:00 输出 00:00:00 - 第一个区间的开始 for 每个相邻的区间对 (A, B): if A的结束 < B的开始 输出 A的结束 - B的开始 if 最后一个区间的结束 < 23:59:59 输出 最后一个区间的结束 - 23:59:59

3. 完整代码实现与解析

基于上述思路，我们可以实现完整的解决方案。以下是使用C++ STL的详细代码：

#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Time { int h, m, s; static Time fromString(const string& str) { Time t; sscanf(str.c_str(), "%d:%d:%d", &t.h, &t.m, &t.s); return t; } int toSeconds() const { return h * 3600 + m * 60 + s; } string toString() const { char buffer[9]; sprintf(buffer, "%02d:%02d:%02d", h, m, s); return string(buffer); } }; void printGap(const Time& start, const Time& end) { cout << start.toString() << " - " << end.toString() << endl; } int main() { int N; cin >> N; cin.ignore(); // 消耗换行符 vector<pair<Time, Time>> intervals; for (int i = 0; i < N; ++i) { string line; getline(cin, line); Time start = Time::fromString(line.substr(0, 8)); Time end = Time::fromString(line.substr(11, 8)); intervals.emplace_back(start, end); } // 按开始时间排序 sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) { return a.first.toSeconds() < b.first.toSeconds(); }); // 检查开始前的间隙 Time dayStart = Time{0, 0, 0}; if (intervals[0].first.toSeconds() > dayStart.toSeconds()) { printGap(dayStart, intervals[0].first); } // 检查中间间隙 for (size_t i = 0; i < intervals.size() - 1; ++i) { const auto& curr = intervals[i]; const auto& next = intervals[i+1]; if (curr.second.toSeconds() < next.first.toSeconds()) { printGap(curr.second, next.first); } } // 检查结束后的间隙 Time dayEnd = Time{23, 59, 59}; if (intervals.back().second.toSeconds() < dayEnd.toSeconds()) { printGap(intervals.back().second, dayEnd); } return 0; }

代码关键点解析：

1. Time结构体封装了时间处理逻辑，包括字符串转换和秒数计算
2. 使用vector<pair<Time, Time>>存储时间区间，比直接处理字符串更清晰
3. 排序使用lambda表达式，按开始时间的秒数比较
4. 三个检查步骤分别处理开始前、中间和结束后的间隙

4. 优化与边界条件处理

在实际编码中，我们需要特别注意一些边界条件和可能的优化点：

4.1 输入处理优化

原始代码中直接使用字符串比较，虽然简单但不够健壮。我们改进后的版本将时间转换为结构体，具有以下优势：

• 更清晰的类型系统
• 更容易进行时间计算和比较
• 减少字符串操作错误

4.2 边界条件检查

需要特别注意以下几种边界情况：

1. 只有一个时间区间的情况
2. 时间区间正好从00:00:00开始或到23:59:59结束
3. 相邻区间端点恰好重合的情况（题目保证不会重叠，但可能端点重合）

测试用例示例：

输入： 1 12:00:00 - 13:00:00 输出： 00:00:00 - 12:00:00 13:00:00 - 23:59:59

4.3 性能分析

• 时间复杂度：O(N log N)，主要由排序步骤决定
• 空间复杂度：O(N)，存储所有时间区间
• 对于PTA天梯赛的数据规模(N ≤ 1000)，这个算法完全足够

5. 常见错误与调试技巧

在解决这类区间问题时，初学者常会遇到一些典型错误：

5.1 时间比较错误

直接使用字符串比较时间可能导致错误结果：

// 错误示例：字符串比较 if ("08:59:59" < "09:00:00") // 可能正确，但不推荐

正确做法是转换为秒数或使用专门的时间结构体比较。

5.2 区间端点处理不当

题目说明区间至少间隔1秒，且不会重叠，但可能有端点重合。例如：

07:10:59 - 08:00:00 08:00:00 - 09:00:00

这两个区间是连续的，中间没有间隙，不应输出。

5.3 输入格式处理

使用getline读取输入时，需要注意处理换行符：

cin >> N; cin.ignore(); // 消耗掉数字后的换行符

5.4 输出格式要求

输出必须严格匹配题目要求的格式，包括前导零和分隔符：

04:30:00 - 05:30:00 // 正确 4:30:0 - 5:30:0 // 错误

6. 扩展思考与实际应用

这道题目虽然来自算法竞赛，但其核心思想在实际开发中有广泛应用：

1. 日程安排系统：检测用户日程表中的空闲时间段
2. 资源预订系统：找出未被预订的时间段
3. 日志分析：识别系统活动中的静默期
4. 网络监控：发现服务中断的时间窗口

理解这类区间处理问题的通用解法，可以帮助我们解决许多实际问题。例如，在处理会议室预订系统时，类似的算法可以用来查找可用的时间段。

进一步挑战：

• 如果时间区间可能重叠，如何合并区间后再找间隙？
• 如果需要处理跨越多天的时间段，算法该如何调整？
• 如何优化算法以处理大规模数据（如N > 1,000,000）？

7. 竞赛技巧与STL使用心得

在算法竞赛中，合理使用STL可以大幅提高编码效率和正确率。对于这道题，我们主要使用了：

• vector：动态数组，存储时间区间
• sort：对区间进行排序
• pair：组合开始和结束时间

STL使用建议：

1. 熟悉常用容器的接口和特性
2. 掌握自定义比较函数的方法（lambda表达式很实用）
3. 注意迭代器的有效性和边界条件
4. 对于复杂数据结构，考虑定义辅助类型（如我们的Time结构体）

在最近的PTA天梯赛中，这类考察基础数据结构应用和问题分解能力的题目越来越常见。通过这道题，我们不仅学会了如何处理时间区间，更重要的是培养了将实际问题抽象为计算模型的能力。