algorithm - 查找给定开始和结束时间的并发事件数

Question

我有大量(~10⁹)事件，这些事件以开始时间和结束时间为特征。给定一个时间，我想找出当时正在进行的这些事件中有多少。

在这种情况下，什么样的数据结构会有所帮助？我需要快速的操作是:

1. 插入新事件，例如，{start: 100000 milliseconds, end: 100010 milliseconds}。
2. 查询给定时间的并发事件数。

---

更新:有人在上面放了一个计算几何标志，所以我想我应该用计算几何来重新表述它。我有一组一维间隔，我想计算这些间隔中有多少与给定点相交。新间隔的插入必须很快。

Answer 1

您正在寻找 interval tree .

• 构造:O(n log n)，其中n是区间数
• 查询:O(m+log n)，其中m为查询结果数，n为区间数
• 空间:O(n)