from banyan import SortedSet, OverlappingIntervalsUpdator # pip install banyan
def maximize_nonoverlapping_count(intervals):
# build "interval" tree sorted by the end-point O(n log n)
tree = SortedSet(intervals, key=lambda (start, end): (end, (end - start)),
updator=OverlappingIntervalsUpdator)
result = []
while tree: # until there are intervals left to consider
# pop the interval with the smallest end-point, keep it in the result
result.append(tree.pop()) # O(log n)
# remove intervals that overlap with the popped interval
overlapping_intervals = tree.overlap(result[-1]) # O(m log n)
tree -= overlapping_intervals # O(m log n)
return result
banyan supports deleting intervals from the tree. For example, to remove a minimal number of intervals from a list of intervals such that the intervals that are left do not overlap in O(n log n), banyan.SortedSet (augmented red-black tree) could be used:
from banyan import SortedSet, OverlappingIntervalsUpdator # pip install banyan
def maximize_nonoverlapping_count(intervals):
# build "interval" tree sorted by the end-point O(n log n)
tree = SortedSet(intervals, key=lambda (start, end): (end, (end - start)),
updator=OverlappingIntervalsUpdator)
result = []
while tree: # until there are intervals left to consider
# pop the interval with the smallest end-point, keep it in the result
result.append(tree.pop()) # O(log n)
# remove intervals that overlap with the popped interval
overlapping_intervals = tree.overlap(result[-1]) # O(m log n)
tree -= overlapping_intervals # O(m log n)
return result
Maybe storing of all intersection intervals can help.
You need:
boundaries of union of all intervals,
for each intersection left boundary and list of intervals from which intersection is made.
Intersection intervals can be stored in a tree, because they are represented only with left boundary. Methods insert and delete interval look like (simplified):
Insert: find intersection intervals for left and right boundary of new interval, split these intersection intervals in 2 or 3 new intersection intervals. For each intersection intervals between add pointer to new interval.
Delete: find intersection intervals for left and right boundary, merge them to intersection intervals before. For each intersection intervals between remove pointer to deleted interval.
发布评论
评论（3）
banyan支持从树中删除区间。例如，要从间隔列表中删除最少数量的间隔，以便剩下的间隔在O(n log n)中不会重叠，banyan.SortedSet（增强红黑树）可以使用：示例：
请参阅Python - 删除重叠列表。
banyansupports deleting intervals from the tree. For example, to remove a minimal number of intervals from a list of intervals such that the intervals that are left do not overlap inO(n log n),banyan.SortedSet(augmented red-black tree) could be used:Example:
See Python - Removing overlapping lists.
也许存储所有交叉点间隔会有所帮助。
您需要：
交叉点间隔可以存储在树中，因为它们仅用左边界表示。插入和删除间隔的方法如下（简化）：
插入：找到新间隔的左右边界的交集间隔，将这些交集间隔分成 2 或 3 个新的交集间隔。对于每个交集间隔，添加指向新间隔的指针。
删除：找到左右边界的交集间隔，将它们合并到之前的交集间隔。对于删除指针到已删除间隔之间的每个交集间隔。
Maybe storing of all intersection intervals can help.
You need:
Intersection intervals can be stored in a tree, because they are represented only with left boundary. Methods insert and delete interval look like (simplified):
Insert: find intersection intervals for left and right boundary of new interval, split these intersection intervals in 2 or 3 new intersection intervals. For each intersection intervals between add pointer to new interval.
Delete: find intersection intervals for left and right boundary, merge them to intersection intervals before. For each intersection intervals between remove pointer to deleted interval.
如果您正在寻找处理间隔算术的 Python 库，请考虑 python -间隔。免责声明：我是该库的维护者。
该库支持检查重叠并自动合并间隔。例如：
如果您想专门计算重叠：
它支持开/闭区间，有限或无限。要删除给定间隔，只需使用差分运算符：
如果您能更具体一点，我可以帮助您。
If you're looking for a Python library that handles intervals arithmetic, consider python-interval. Disclaimer: I'm the maintainer of that library.
This library has support to check for overlaps, and to automatically merge intervals. For example:
If you want to specifically compute the overlap:
It supports open/closed intervals, finite or infinite. To remove intervals for a given one, just use the difference operator:
I can help you if you can be a little bit more specific.