定義
父記錄具有型別“P”、祖先鍵和日期間隔。
它的子記錄具有型別“C”，一個相同的祖先鍵，并且具有匹配或落在其父間隔內的日期間隔。
- 所有記錄都是唯一的
- 父記錄可以共享同一個祖先鍵，但它們的日期間隔不能重疊
- 一個父記錄可以有多個子記錄
例子
父記錄可以是：
- 電話, 12345, (1000-01-01, 1000-12-31)
- P, 12345, (1001-01-01, 1001-12-31) // 無重疊日期，有效
第一個父記錄的有效子記錄可以是
- C, 12345, (1000-01-01, 1000-12-31) // 匹配所有內容，有效
- C, 12345, (1000-05-05, 1000-09-09) // 匹配祖先鍵，在父日期間隔內，有效
問題
給定一組包含父母和孩子的隨機記錄，我如何根據鍵和時間間隔將集合有效地分為一個唯一的父母及其有效孩子的不同組？
保證每個孩子都有一位且只有一位家長。但有可能父母沒有任何孩子。
蠻力解決方案
在線性時間內識別所有父記錄。然后回圈遍歷它們并在平方時間內成對匹配所有其他記錄。
題
有沒有更快的方法？
uj5u.com熱心網友回復：
最簡單的方法是制作一個 P 記錄串列和 C 記錄串列，然后將它們按 (ancestor_key, interval.start)
然后遍歷父串列，對于每個父串列，從子串列中提取它的子節點。由于排序，父子串列會按照對應的順序排列，所以兩個串列中感興趣的位置只會向前移動。
總復雜度為 O(n log n)，由排序決定。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/351717.html