★ FEATURED ARTICLE 1. 这道题到底在考什么从标题拆解核心需求CSP-202209-3-防疫大数据这个标题信息量其实很密集。CSP 是计算机软件能力认证的缩写中间的 202209 代表 2022 年 9 月场次末尾的 3 表示这是该场考试的第三题。熟悉这套认证体系的人都知道第三题通常是一道综合性较强的模拟题难度介于前两题的基础算法和第四题的高级数据结构之间往往需要把多个模块串起来才能拿到满分。而防疫大数据这个副标题则直接点明了题目的应用场景——围绕人员流动与风险排查构建一套数据处理逻辑。我在第一次看到这个标题的时候脑子里冒出来的第一个判断是这大概率是一道区间处理加状态维护的题目。为什么这么判断因为防疫大数据这个场景天然涉及时间维度上的行程记录、区域维度的风险标记以及人员维度的状态查询。这三者叠加在一起几乎必然要用到某种形式的时间区间管理结构。后来实际做题验证了这个直觉——题目的核心确实是在一堆带时间戳的行程记录和风险区域公告之间维护每个人员在不同时刻的风险状态。这道题适合谁来啃如果你已经能熟练写出基础的排序、二分查找、简单的模拟逻辑那么这道题是一个非常好的进阶练习。它不会要求你掌握线段树或者树状数组那种重型武器但对离散化思想、区间合并、状态转移的边界处理有相当扎实的考察。对于准备参加同类认证考试的同学来说这道题的价值在于它逼着你去想清楚一个时刻到底属于哪个区间这种看似简单实则容易翻车的细节。从更宏观的视角看这道题背后的真实需求是给定一批人员的行程记录谁在什么时间段去了哪个区域再给定一批风险区域的公告某个区域在某个时间段被标记为风险要求判断某个人员在某一天是否属于风险人群。这个判断逻辑在现实世界里对应的是流调排查的核心环节只不过题目把它抽象成了确定性的规则计算。理解了这层映射关系你就能明白为什么题目要在时间区间的开闭、风险等级的判定上设置那么多细节——现实中的防疫规则本身就是层层嵌套的。2. 题目规则的全景拆解与方案选型2.1 三类实体与它们之间的关系把题目读透之后我发现它其实只涉及三类实体人员、区域、行程记录。人员有编号区域有编号行程记录则是一条某人在某天去了某区域的三元组。除此之外还有一类动态信息风险区域的公告形式是某区域从某天起被标记为风险直到某天解除。这里的关键在于风险状态不是静态的而是随时间变化的。一个区域可能在第 1 天到第 5 天是风险区第 6 天解除第 10 天又因为新情况重新被标记。这种反复横跳的特性决定了我们不能简单地用一个布尔值来记录区域是否风险而必须维护一个时间区间集合。我当时的思路是这样的对每个区域维护一个风险时间段的列表每个时间段用左闭右闭或者左闭右开的区间表示。当有新的公告到来时把新区间合并进去注意处理重叠和相邻的情况。对每个人则维护他的行程记录列表。查询时遍历这个人的所有行程看是否存在某条行程的时间段与某个风险区域的风险时间段有交集。这个思路的时间复杂度取决于数据规模。如果行程记录总数是 N风险区间总数是 M那么最朴素的查询是 O(N×M) 的。在实际考试的数据范围内这个复杂度往往能过大部分测试点但如果追求满分就需要在区间合并和查询上做优化。2.2 为什么选择区间合并而不是逐天标记这里有一个很自然的岔路口一种做法是把每一天都当成一个独立的点用一个巨大的数组或者哈希表记录第 i 天区域 j 是否风险查询时直接查表。另一种做法就是我上面说的区间合并。逐天标记的好处是查询 O(1)非常直观。但它的致命问题在于时间跨度可能非常大。题目里的日期虽然通常在一个可控范围内但如果出题人把日期设到很大的数值逐天标记就会爆内存。而且逐天标记在合并新区间时需要遍历区间内的每一天如果区间很长更新成本也很高。区间合并则把连续的风险天压缩成一个区间对象存储成本只与公告数量有关与时间跨度无关。查询时虽然需要做区间相交判断但一次判断是 O(1) 的整体查询成本是 O(行程数 × 该区域的风险区间数)。在公告数量不大的情况下这个方案明显更优。提示区间合并时一定要想清楚开闭关系。题目里从第 L 天到第 R 天是风险通常意味着 L 和 R 都包含在内也就是左闭右闭。但如果你在代码里用左闭右开表示就要在合并和查询时统一转换千万别一半用一种表示法。2.3 离散化把稀疏的时间点压缩成紧凑的索引虽然区间合并已经避免了逐天存储但在某些实现里我们仍然需要对时间点做排序和去重这时候离散化就派上用场了。所谓离散化就是把所有出现过的日期收集起来排序去重然后用它们在排序后数组中的下标来代替原始日期。这样做的好处是原本可能跨度很大的日期值被映射到了 0 到 K-1 的紧凑整数上K 是不同日期的数量后续无论是做二分查找还是建索引都更方便。举个具体的例子假设出现的日期是 1、5、100、1000离散化之后就变成 0、1、2、3。原来判断第 50 天是否在区间 [1,100] 内需要比较数值离散化后可以先二分找到 50 落在哪两个离散点之间再做判断。对于这道题来说离散化的主要价值在于让区间端点的处理更加规整减少因为日期值跳跃带来的边界错误。不过要提醒一句离散化不是万能的。如果题目要求精确到某一天的判断而你的离散化只保留了出现过的日期那么对于那些没出现在任何记录里的日期你需要额外处理它们落在哪个离散区间。这道题里查询的日期一定是行程记录里出现过的日期所以这个问题不突出但换一道题就未必了。3. 核心数据结构的落地实现细节3.1 风险区间的存储与合并逻辑我最终选择的结构是这样的用一个哈希表或者数组如果区域编号连续且范围不大来存储每个区域的风险区间列表。列表里的每个元素是一个二元组 (l, r)表示从第 l 天到第 r 天是风险期。当来一条新公告 (区域 d起始天 l结束天 r) 时我需要把这个区间插入到该区域的区间列表中并保持列表有序且互不重叠。具体操作分三步把新区间加入列表。按左端点排序。从头扫描合并重叠或相邻的区间。合并的判断条件是如果当前区间的左端点小于等于前一个区间的右端点加一注意这里加一是因为相邻的区间也可以合并比如 [1,3] 和 [4,6] 合并成 [1,6]就把它们合并。合并后的右端点取两者右端点的较大值。这个逻辑写起来不复杂但有一个坑我踩过合并后列表的长度会变化如果用 for 循环边遍历边删除很容易越界或者漏掉元素。稳妥的做法是新建一个结果列表把合并后的区间依次放进去最后用结果列表替换原列表。这样虽然多了一次内存分配但逻辑清晰不容易出错。def merge_intervals(intervals): if not intervals: return [] intervals.sort(keylambda x: x[0]) merged [intervals[0]] for l, r in intervals[1:]: if l merged[-1][1] 1: merged[-1] (merged[-1][0], max(merged[-1][1], r)) else: merged.append((l, r)) return merged上面这段代码就是合并的核心。注意merged[-1][1] 1这个细节它处理了相邻区间的情况。如果你的题目规则里相邻不算连续那就去掉这个加一。这道题里相邻是算连续的因为第 3 天风险、第 4 天也风险中间没有间隔理应合并。3.2 行程记录的索引方式行程记录的存储相对简单但查询效率取决于你怎么组织它。最直接的方式是用一个字典键是人员编号值是这个人的行程列表每条行程是 (区域, 起始天, 结束天)。查询某人某天是否风险时遍历他的行程对每条行程检查两件事该行程涉及的区域在那个时间点是否处于风险期以及该行程的时间段是否覆盖查询日期。这里有一个优化点值得说如果一个人的行程很多而查询也很多那么每次都全量遍历他的行程会很慢。一个常见的做法是按时间对行程排序然后用二分查找定位可能覆盖查询日期的行程。不过这道题的数据规模下线性遍历通常够用除非你追求极致性能。我在实现时还加了一个小优化对于每条行程预先判断它涉及的区域的整体风险时间范围即该区域所有风险区间的最小左端点和最大右端点。如果查询日期根本不在这条行程的时间段内直接跳过连区域风险判断都省了。这个剪枝在行程时间段普遍较短时效果明显。3.3 查询逻辑的精确表达查询是整道题最容易出错的地方因为涉及两个时间段的相交判断。设行程时间段为 [a, b]风险时间段为 [c, d]两者有交集的条件是a d 且 c b。这个条件看起来简单但我在实际写的时候犯过一个错把有交集和行程完全在风险期内搞混了。题目要求的是如果一个人在风险期内到访过风险区域就算风险人员。也就是说只要行程时间段和风险时间段有任何重叠哪怕只重叠一天也算。所以用上面的相交条件是对的。但如果你误写成行程必须完全包含在风险期内就会漏掉很多情况。还有一种边界情况行程的起始天等于风险期的结束天或者行程的结束天等于风险期的起始天。按照相交条件这两种情况都算有交集因为 a d 且 c b 在等号成立时依然为真。这符合题目到访过的语义——哪怕只在风险期的最后一天到访也算到访过。注意如果题目对到访的定义是在风险期内停留过至少一整天那么边界情况就要重新考虑。做题时一定要回到题面确认语义不要想当然。4. 完整实操流程与关键环节演示4.1 输入解析与数据预处理拿到输入后第一步是把所有数据读进来并分类。通常输入会先给出人员数量、区域数量、行程记录数量、公告数量等元信息然后是具体的记录。我习惯用一个统一的读取函数把每行拆成字段然后根据记录类型分发到不同的处理逻辑。预处理阶段要做的事情包括收集所有出现过的日期用于可能的离散化、初始化每个区域的风险区间列表为空、初始化每个人的行程列表为空。这一步看似琐碎但它是后续所有逻辑的基础如果这里漏了某个区域的初始化后面查询时就会遇到键不存在的错误。我一般会用defaultdict(list)来避免手动初始化每个键这样访问不存在的键时会自动创建空列表。这个小技巧能省掉不少样板代码也减少了因为忘记初始化而导致的 bug。4.2 公告处理与区间维护的时序问题公告是动态到来的每来一条就要更新对应区域的风险区间。这里有一个时序上的细节公告本身可能带有生效时间也就是说一条公告描述的是从第 L 天起该区域成为风险区但这个公告是在某个时刻才发布的。题目通常会保证公告按某种顺序给出或者要求你按时间顺序处理。如果公告不是按时间顺序给出的你就不能简单地边读边合并而应该先把所有公告收集起来按生效时间排序后再统一合并。我在第一次做的时候就是边读边合并结果因为公告顺序混乱导致区间合并出错。后来改成先收集后排序问题就解决了。这个教训说明凡是涉及时间区间的题目先问自己输入是否有序如果无序排序是第一步。不要假设输入友好出题人最喜欢在顺序上做文章。4.3 查询批处理与结果输出查询通常是一批一批来的每条查询给出一个人和一天要求输出该人当天是否风险。我的做法是把查询也收集起来然后逐条处理。对于每条查询取出该人的行程列表遍历检查是否有行程与风险区间相交。如果查询量很大可以考虑把查询按人员分组这样同一个人的多条查询可以共享行程列表的遍历结果。不过这道题里查询量通常不会大到需要这种优化线性处理即可。输出格式要严格按照题目要求通常是每行一个结果用特定的字符串表示风险或安全。我在输出时犯过一个低级错误把布尔值直接打印出来结果输出的是 True/False 而不是题目要求的 Yes/No。这种错误完全可以通过仔细读题避免但考试时紧张就容易忽略。4.4 一个完整的模拟案例走查假设有 2 个人员、2 个区域。行程记录人员 1 在第 1 到 3 天去了区域 A人员 2 在第 5 天去了区域 B。公告区域 A 从第 2 天到第 4 天是风险区区域 B 从第 6 天起是风险区假设持续到第 10 天。查询人员 1 第 2 天是否风险人员 2 第 5 天是否风险人员 2 第 7 天是否风险逐条分析人员 1 的行程 [1,3] 与区域 A 的风险期 [2,4] 相交交集是 [2,3]所以第 2 天是风险。人员 2 的行程是第 5 天单天 [5,5]区域 B 的风险期从第 6 天开始[5,5] 与 [6,10] 不相交所以第 5 天安全。人员 2 第 7 天没有行程记录他只在第 5 天去过区域 B所以第 7 天也安全——注意这里容易误判因为区域 B 在第 7 天确实是风险区但人员 2 当天并不在区域 B所以不算风险。这个案例清楚地展示了区域风险和人员风险的区别区域风险是客观状态人员风险取决于他是否在风险期到访过风险区域。两者不能混为一谈。5. 常见问题排查与避坑经验实录5.1 区间合并的典型错误对照表错误现象根本原因修正方法合并后区间数量偏多相邻区间未合并判断条件用l prev_r 1合并后区间覆盖范围偏小合并时右端点取了较小值右端点取max(prev_r, r)部分区间丢失边遍历边删除导致索引错乱新建结果列表不原地修改区间顺序混乱未排序直接合并合并前按左端点排序这张表里的每一条我都实际遇到过。尤其是第三条当时用了一个列表的remove方法在循环里删元素结果删着删着就跳过了某些区间排查了半天才发现是迭代器失效的问题。后来养成习惯凡是需要过滤或合并列表一律新建列表不在原列表上动刀。5.2 时间边界处理的三个高频陷阱第一个陷阱是开闭区间混用。有的地方用左闭右闭有的地方用左闭右开结果在判断相交时条件写错。我的建议是全程统一用一种表示法并且在代码注释里明确写出来比如# 区间统一为左闭右闭 [l, r]。第二个陷阱是单天行程的处理。如果一个人只在某一天去了某区域行程时间段是 [d, d]这是一个合法的闭区间。判断相交时它和任何包含 d 的风险区间都相交。但如果你在代码里把单天行程当成特殊情况跳过就会漏判。第三个陷阱是公告的生效与失效。有的公告说从第 L 天起成为风险区没有明确结束时间可能意味着持续到某个默认终点。这种模糊表述一定要回到题面找定义不要自己臆断。如果题面说直到另行通知那就要看后续是否有解除公告没有的话可能默认持续到查询范围的末尾。5.3 性能瓶颈的定位与优化如果代码在大数据量下超时先别急着换算法用排除法定位瓶颈。常见的瓶颈有三个区间合并时的排序、查询时的全量遍历、以及频繁的字典查找。排序的优化空间不大除非你能保证输入有序。查询遍历的优化前面提过可以按时间排序后二分。字典查找的优化则是尽量用数组代替字典如果区域编号和人员编号都是连续的小整数直接用列表索引会比字典快不少。我实测下来这道题在常规数据范围内朴素的区间合并加线性查询就能过。真正卡人的往往不是性能而是边界条件的正确性。所以与其花时间优化常数不如多造几组边界数据自测。5.4 自测数据的构造思路自己造测试数据是排查问题的利器。我通常构造四类数据全是单天行程的、行程和风险期刚好错开一天的、风险期有重叠和相邻的、以及查询日期落在各种边界上的。这四类数据能覆盖绝大多数边界情况。特别是刚好错开一天这类数据最能暴露开闭区间处理错误。比如行程是 [1,3]风险期是 [4,6]正确答案是不相交但如果你的相交条件写成了a d漏了等号的另一侧就可能误判为相交。反过来行程 [1,4] 和风险期 [4,6] 是相交的共享第 4 天如果你的条件写成了严格小于就会漏判。6. 从这道题延伸出的通用方法论做完这道题之后我最大的体会是区间类问题的核心不在于数据结构多高级而在于把区间这个概念在代码里表达得足够精确。什么叫精确就是每一个区间的开闭、每一个相交判断的等号、每一次合并的边界你都能说清楚为什么是这样而不是那样。很多人在区间题上翻车不是因为不会算法而是因为脑子里对区间的定义是模糊的写出来的代码自然就带着模糊。另一个体会是关于状态的时间维度。这道题里区域的风险状态是随时间变化的人员的行程也是带时间段的。当两个带时间维度的东西需要做匹配时最稳妥的做法是把它们都化成区间然后用区间相交来判断。这个套路可以迁移到很多场景比如判断两个任务的时间是否冲突、判断某个事件是否落在某个窗口内、判断资源占用是否有重叠。掌握了区间相交这一个基本操作一大类问题就有了统一的解法框架。最后说一个实操上的小习惯。我现在写这类题会先在纸上画一条时间轴把行程和风险期都画上去用不同颜色标出重叠部分。画完之后边界情况一目了然代码写起来也更有底气。这个习惯看起来笨但比在脑子里空想靠谱得多。尤其是考试环境下时间紧张纸上画两笔反而能省下调试的时间。如果你也在准备类似的认证考试我的建议是不要只满足于能过样例而是每道题都逼自己想清楚如果数据再刁钻一点我的代码会不会挂。这种自我刁难的过程才是真正把一道题吃透的关键。防疫大数据这道题的价值恰恰在于它用看似简单的规则逼着你在时间区间的边界上反复较真。把这道题啃下来以后再遇到区间合并、时间匹配类的题目心里就有底了。
阅读完成 · 觉得有帮助？
