防疫大数据这道题，当年在考场上放倒了一大片人。题目本身不复杂，难的是把"时空伴随"这种现实概念翻译成可计算的数据结构，还要在时限内跑通。我后来拿这道题做过好几次教学复盘，发现大多数人卡住的地方惊人地一致：不是算法不会，而是没想清楚"一个人什么时候算有风险"这件事该怎么用代码表达。这篇就把这道题从需求拆解到代码落地完整走一遍，重点讲清楚每一步为什么这么设计，以及实测中容易翻车的细节。

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 有交集"。

于是自然的拆法是两层：

1. 人员 → 该人员去过的场所及时间：回答"p 在 t 时刻在哪"。
2. 场所 → 该场所的所有记录（含时间区间和是否确诊）：回答"这个场所此刻有没有风险源"。

第一层用哈希表人员编号 → 记录列表，第二层用哈希表场所编号 → 记录列表。两个表在输入阶段一次性建好，查询时都是 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, b+w]。这样判断就统一成了"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 拖慢）。写完代码先问自己两个问题：边界用例覆盖了吗？最坏规模下跑得动吗？这两个问题答上来，这道题基本就稳了。我带人复盘时，通常让他们先不看代码，只口述这两个问题的答案，能说清楚的人，代码质量普遍不差。