如何基于键值和时间区间高效查找父记录并匹配分组子记录

定义 #

• 父记录类型为P，包含ancestor key、日期区间两个核心属性
• 子记录类型为C，需同时满足两个条件：1. 持有与父记录完全相同的ancestor key；2. 自身日期区间与父记录区间完全匹配，或完全落在父记录区间范围内

其他约束：

• 所有记录唯一
• 多个父记录可共享同一个ancestor key，但彼此的日期区间不得重叠
• 一个父记录可对应多个子记录

示例 #

合法父记录参考：

• P, 12345, (1000-01-01, 1000-12-31)
• P, 12345, (1001-01-01, 1001-12-31) // 同ancestor key下日期间隔无重叠，符合规则

上述第一条父记录对应的合法子记录参考：

• C, 12345, (1000-01-01, 1000-12-31) // 所有属性完全匹配，符合规则
• C, 12345, (1000-05-05, 1000-09-09) // ancestor key匹配，日期区间完全在父记录范围内，符合规则

问题描述 #

给定包含父、子记录的随机数据集，需按照ancestor key和时间区间匹配规则，将数据划分为多个分组，每个分组包含唯一父记录及其所有合法子记录。已知每个子记录有且仅有一个对应父记录，允许父记录无匹配子记录。

暴力解法 #

先线性遍历筛选所有父记录，再遍历每个父记录与其余所有记录逐一匹配，时间复杂度为平方级O(n²)，数据量较大时性能极差。

优化实现方案 #

存在时间复杂度为O(n log n)的高效实现方案，核心利用了同ancestor key下父记录区间不重叠的约束，具体步骤如下：

1. 拆分记录：一次线性遍历所有记录，拆分得到父记录集合、子记录集合，时间复杂度O(n)，n为总记录数。
2. 父记录预处理：
   • 用哈希表对父记录按ancestor key分组，哈希表的key为ancestor key，value为对应key下的所有父记录列表
   • 对每个key下的父记录列表，按区间起始时间升序排序，因为同key下父记录区间无重叠，排序后得到的是一组连续不重叠的有序区间，该步骤整体时间复杂度为O(m log m)，m为父记录总数。
3. 子记录匹配：
   遍历所有子记录，每个子记录按如下逻辑匹配父记录：
   • 按自身ancestor key从哈希表中取出对应的父记录有序列表
   • 用二分查找在有序父记录列表中，找到满足「父区间起始时间 ≤ 子区间起始时间，且父区间结束时间 ≥ 子区间结束时间」的唯一父记录，将子记录归入该父记录的分组。该步骤整体时间复杂度为O(c log m)，c为子记录总数，满足m + c = n。

实现说明 #

• 因为同ancestor key下的父记录区间无重叠，所以二分查找结果唯一，不会出现匹配到多个父记录的情况，完全符合题目给定的约束。
• 该方案实现简单，不需要引入复杂的数据结构，常规编程语言的标准库都自带哈希表和二分查找实现，可直接调用。
• 如果存在大量高频匹配需求，也可以改用区间树存储父记录，单次查询时间复杂度同样为O(log k)，但实现复杂度更高，一般场景下排序+二分的方案性价比最高。

内容的提问来源于stack exchange，提问作者valeesi