intervaltree 是一个用于高效处理区间（interval）操作的 Python 库，常用于处理时间区间、数字区间等的查询和重叠检测。它基于二叉搜索树（红黑树）实现，支持快速插入、删除和区间查询操作。

以下是 intervaltree 库的详细用法：

安装
pip install intervaltree

基本概念

• Interval 对象：表示一个区间，包含 begin（起点）、end（终点）和可选的 data（附加数据）。
• IntervalTree 类：存储和管理多个 Interval 对象，支持高效查询。

创建 Interval 对象

python

复制

下载

from intervaltree import Interval, IntervalTree

# 创建一个区间 [1, 5)，附加数据为 "data1"
interval = Interval(1, 5, "data1")

创建 IntervalTree

python

复制

下载

# 创建一个空的 IntervalTree
tree = IntervalTree()

# 添加区间
tree.add(Interval(1, 5, "data1"))
tree.add(Interval(3, 8, "data2"))
tree.add(Interval(6, 10, "data3"))

# 或者通过列表初始化
intervals = [Interval(1, 5), Interval(3, 8), Interval(6, 10)]
tree = IntervalTree(intervals)

基本操作

1. 添加区间

python

复制

下载

tree.add(Interval(10, 15, "new_data"))

2. 删除区间

python

复制

下载

# 删除指定区间
interval_to_remove = tree.pop()  # 删除并返回一个区间
tree.remove(Interval(1, 5))       # 删除特定区间（必须完全匹配）

# 根据条件删除
tree.remove_overlap(4, 7)  # 删除所有与 [4,7) 重叠的区间
tree.remove_envelop(2, 6)  # 删除所有被 [2,6) 包含的区间

3. 查询区间

python

复制

下载

# 查找所有与某个点重叠的区间
result = tree.at(4)  # 返回所有包含点 4 的区间

# 查找所有与某个区间重叠的区间
result = tree.overlap(2, 7)  # 返回所有与 [2,7) 重叠的区间

# 查找完全包含某个区间的区间
result = tree.envelop(3, 5)  # 返回所有包含 [3,5) 的区间

# 查找被某个区间完全包含的区间
result = tree.covered_by(2, 6)  # 返回所有被 [2,6) 包含的区间

4. 遍历所有区间

python

复制

下载

for interval in tree:
    print(interval.begin, interval.end, interval.data)

高级操作

1. 合并重叠区间

python

复制

下载

tree.merge_overlaps()  # 合并所有重叠的区间（原地操作）
merged_tree = tree.merge_overlaps(strict=False)  # 合并并返回新树

2. 切片操作

python

复制

下载

# 截取树中在 [4, 9) 范围内的区间
sliced_tree = tree.slice(4, 9)

3. 区间长度

python

复制

下载

interval = Interval(1, 5)
print(interval.length())  # 输出 4

4. 区间关系判断

python

复制

下载

interval1 = Interval(1, 5)
interval2 = Interval(3, 7)

print(interval1.overlaps(interval2))  # True
print(interval1.contains(2))          # True

实际应用示例

场景：检测时间区间冲突

python

复制

下载

# 创建时间区间树
schedule = IntervalTree()
schedule.add(Interval(9, 10, "Meeting"))
schedule.add(Interval(11, 12, "Lunch"))
schedule.add(Interval(14, 16, "Work"))

# 检查新事件 [10, 11) 是否冲突
conflicts = schedule.overlap(10, 11)
if conflicts:
    print("冲突事件：", [i.data for i in conflicts])
else:
    print("无冲突")

注意事项

1. 区间范围：区间是左闭右开的，即 [begin, end)。
2. 性能：插入和查询的时间复杂度为 O(log n)，适合处理大量区间。
3. 数据附加：可以通过 data 字段为区间附加额外信息。

官方文档

• GitHub 仓库: https://github.com/chaimleib/intervaltree

通过灵活使用 intervaltree，你可以高效处理复杂的区间操作问题。