防疫大数据这道题当年在考场上放倒了一大片人。题目本身不复杂难的是把时空伴随这种现实概念翻译成可计算的数据结构还要在时限内跑通。我后来拿这道题做过好几次教学复盘发现大多数人卡住的地方惊人地一致不是算法不会而是没想清楚一个人什么时候算有风险这件事该怎么用代码表达。这篇就把这道题从需求拆解到代码落地完整走一遍重点讲清楚每一步为什么这么设计以及实测中容易翻车的细节。1. 先把防疫大数据翻译成可计算的问题1.1 题目到底在问什么这道题的核心场景是给定一批人员的行程记录谁在什么时间段去过哪个场所再给定一批查询要求判断某个时刻某个人是否属于风险人群。风险的定义来自两条规则——直接接触和时空伴随。直接接触好理解就是和确诊者在同一场所、同一时间段有过交集时空伴随则是指在同一场所、时间上有重叠但未必同时出现的情况具体判定依赖题目给定的时间窗口。很多人一上来就开始写代码结果写到一半发现时间段重叠这个判断到处都要用却写了好几份不一样的逻辑最后自己都搞不清哪份是对的。我的建议是先把所有涉及时间的判断抽象成一个统一的函数后面所有规则都调它。这一步想清楚了后面就是纯粹的工程活。题目给的输入规模不小人员数量、记录条数、查询条数都可能上万甚至更多。这意味着你不能用每次查询都全量扫一遍所有记录的暴力思路必须提前把数据组织好让查询接近常数时间或对数时间。这是整道题的性能命门。1.2 三个必须提前想清楚的概念在动手之前有三个概念必须先定义清楚否则代码写到后面一定返工时间段的表示一条记录是从时刻 a 到时刻 b查询是在时刻 t。判断 t 是否落在 [a, b] 内边界要不要算题目通常明确包含端点这个细节错了会直接导致答案偏差。场所的标识场所有编号用编号做键最省事。不要用名字做键字符串比较慢且容易出问题。人员的标识同理用编号。所有映射关系在输入阶段就建好查询阶段只做查表。我见过有人用人员名字场所名字拼成字符串当键结果数据量一大哈希冲突和字符串拼接的开销直接把时间吃光。用整数编号是这类题的基本功。1.3 为什么不能暴力假设有 N 条记录、M 次查询暴力做法是每次查询遍历所有记录复杂度 O(N×M)。按题目规模这个量级轻松上亿次操作在严格的时限下必超。所以正确的方向是预处理 索引把记录按场所归类把每个场所的记录按时间排序查询时只在这个场所的记录里做二分或区间判断。这样单次查询的代价从全体记录降到单个场所的记录量级差出好几个数量级。提示这道题的性能优化不是可选项而是及格线。先把索引结构设计对再谈代码优雅。2. 数据结构选型为什么是场所 → 时间区间列表2.1 从查询反推存储结构设计数据结构最靠谱的方法是从查询倒推。查询长这样给一个时刻 t 和一个人 p问 p 在 t 时刻是否有风险。要回答这个问题得知道 p 在 t 时刻去过哪些场所然后对每个场所判断这个场所里有没有确诊记录与 t 有交集。于是自然的拆法是两层人员 → 该人员去过的场所及时间回答p 在 t 时刻在哪。场所 → 该场所的所有记录含时间区间和是否确诊回答这个场所此刻有没有风险源。第一层用哈希表人员编号 → 记录列表第二层用哈希表场所编号 → 记录列表。两个表在输入阶段一次性建好查询时都是 O(1) 定位剩下的开销只在列表内部的判断上。2.2 每个场所的记录怎么排场所的记录列表如果无序每次查询还是得线性扫。所以建表时顺手按开始时间排序。排序之后判断时刻 t 是否落在某条记录的区间内就可以用二分找到开始时间 ≤ t 的最后一条记录再看它的结束时间是否 ≥ t。这一步把单场所的判断从 O(k) 降到 O(log k)k 是该场所的记录数。这里有个容易忽略的点同一场所可能有多条记录时间重叠二分找到的那一条不一定就是覆盖 t 的那一条。稳妥的做法是找到位置后向前回溯若干条或者干脆维护一个区间并集结构。考虑到题目规模向前回溯几条通常够用但如果数据构造得刁钻大量重叠区间回溯可能退化。更稳的方案是预处理时把同一场所的重叠区间合并成不相交的区间集合查询时二分一次即可。这个合并操作在输入阶段做代价 O(k log k)摊到每次查询上几乎为零。2.3 确诊记录单独标记判断风险的关键是这个场所的这个时间段里有没有确诊者。所以每条记录除了时间区间还要带一个标记这条记录的人是不是确诊者。查询时只有当覆盖 t 的区间里存在确诊标记这个场所才算风险源。我一开始把确诊者和普通记录混在一起存查询时再过滤结果每次都要多扫一遍。后来改成每个场所维护两个列表全部记录列表和确诊记录列表判断风险时只查确诊列表速度快很多。代价是内存翻倍但在这个规模下完全可接受。结构键值用途人员索引人员编号该人员的记录列表定位某人在某时刻的场所场所全量索引场所编号按时间排序的全部记录辅助判断场所确诊索引场所编号按时间排序的确诊记录快速判断风险源3. 时空伴随的判定逻辑把规则写成可复现的代码3.1 直接接触与时空伴随的区别直接接触是同一场所、同一时间段这个判断很直接两条记录的区间有交集即可。时空伴随则宽松一些它允许时间上有一定偏移本质是在相近的时间出现在同一场所。题目会给出这个偏移的窗口大小比如前后若干时间单位内。关键区别在于直接接触要求区间相交时空伴随要求查询时刻 t 落在某条确诊记录的扩展区间内。所谓扩展区间就是把确诊记录的 [a, b] 向两边各扩一个窗口长度变成 [a-w, bw]。这样判断就统一成了t 是否落在扩展区间内和直接接触共用同一套区间判断逻辑。3.2 区间判断的统一实现把两种规则都归约成点是否落在区间内之后代码就干净了。核心函数大概长这样def in_range(t, start, end): return start t end看着简单但边界处理是重灾区。题目如果说包含端点就必须用如果说不包含就得用。我见过太多人在这里栽跟头测试用例全过、提交挂一半最后发现是端点符号写反了。建议把端点语义写进函数名或注释里比如in_range_closed强迫自己想清楚。3.3 多条件组合时的短路顺序一次查询可能要判断多个场所、多条记录。组合条件时把最可能为假、且判断代价最低的条件放前面利用短路求值省时间。比如先判断这个场所是否有确诊记录哈希查表O(1)没有就直接跳过根本不用做区间二分。这个顺序调整在数据量大时能省下可观的时间。def has_risk(person, t): for place, _ in person_records.get(person, []): confirmed confirmed_index.get(place) if not confirmed: continue if any(in_range_closed(t, s, e) for s, e in confirmed): return True return False上面这段是示意实际还要处理扩展窗口和人员自身记录的时间匹配。但思路是清晰的先做便宜的过滤再做昂贵的判断。4. 实测中真正会翻车的地方4.1 时间窗口的扩展方向搞反时空伴随的窗口是向两边扩不是只往前或只往后。我复盘时见过有人只扩了一边样例能过是因为样例数据恰好只覆盖了一侧。这种错误极难通过肉眼发现必须自己构造t 在确诊记录之前和t 在确诊记录之后两个方向的用例分别验证。4.2 同一人多次去同一场所一个人可能在不同时间多次去同一个场所人员索引里会有多条记录指向同一场所。查询时不能假设一人一场所只有一条记录必须遍历该人员的所有相关记录。漏掉这个假设结果就是部分查询漏判。4.3 确诊者自己算不算风险题目通常规定确诊者本人不参与被判定为风险的查询或者查询里根本不会问确诊者。但如果没读清楚把确诊者自己也判成风险答案就会多出来。输入解析阶段就把确诊者集合单独存一份查询时先查这个集合命中直接按题目规定返回。4.4 大规模输入下的 IO 瓶颈数据量大时输入输出本身可能成为瓶颈。用逐行读取、批量输出的方式避免频繁的小块写操作。Python 里sys.stdin.readline比input快不少输出用列表收集后一次性join写出。这些是竞赛场景的常规操作但很多人只关注算法忽略了 IO 这一环。注意性能问题往往不在算法本身而在你没意识到的常数开销上。字符串拼接、重复的字典查找、不必要的对象创建累积起来就是超时。5. 从这道题能带走的通用方法5.1 从查询倒推结构是可复用的思维这道题最有价值的不是某个具体算法而是从查询形态反推存储结构的方法论。现实中的日志分析、风控判定、实时监控本质都是给定条件快速判断某实体是否命中规则套路完全一致先明确查询长什么样再设计让查询变快的索引。把这个思维练熟遇到同类问题就不会从零开始。5.2 把业务规则归约成少数原语直接接触和时空伴随看着是两条规则归约之后其实是同一个点是否在区间内的原语只是区间构造方式不同。能归约的规则一定要归约否则每加一条规则就多一份重复代码维护成本指数上升。这也是我在实际项目里反复验证过的经验规则再多底层原语往往就那么几个。5.3 边界和规模是两把尺子复盘这道题栽跟头的人基本分两类一类是边界没想清楚端点、扩展方向、自身是否参与一类是规模没处理好暴力超时、IO 拖慢。写完代码先问自己两个问题边界用例覆盖了吗最坏规模下跑得动吗这两个问题答上来这道题基本就稳了。我带人复盘时通常让他们先不看代码只口述这两个问题的答案能说清楚的人代码质量普遍不差。
