python - 使用区间树找出重叠区域

Question

我正在尝试使用区间树来解决这个 problem .下面是我的尝试，但可以理解它不起作用，即它没有返回所有间隔。

一场板球比赛即将举行。该场由一维平面表示。作为一名板球运动员，X 先生最喜欢击球。每个镜头都有一个特定的范围。第 i 个镜头的范围是从 A(i) 到 B(i)。这意味着他最喜欢的击球可以在这个范围内的任何地方。对方球队的每个球员只能在特定范围内上场。玩家可以从 A(i) 到 B(i)。您将获得 X 先生最喜欢的镜头和 M 玩家的射程。

对于某些测试用例，蛮力解决方案超时。我只需要一个想法。

class node:
    def __init__(self, low, high):
        self.left = None
        self.right = None
        self.highest = high
        self.low = low
        self.high = high

class interval:
    def __init__(self):
        self.head = None
        self.count = 0

    def add_node(self, node):
        if self.head == None:
            self.head = node
        else:
            if self.head.highest < node.high:
                self.head.highest = node.high         
            self.__add_node(self.head, node)

    def __add_node(self, head, node):                   
        if node.low <= head.low:         
            if head.left == None:            
                head.left = node
            else:            
                if head.left.highest < node.high:
                    head.left.highest = node.high
                self.__add_node(head.left, node)
        else:           
            if head.right == None:                
                head.right = node
            else:               
                if head.right.highest < node.high:
                    head.right.highest = node.high          
                self.__add_node(head.right, node)

    def search(self, node):
        self.count = 0
        return self._search(self.head, node)

    def _search(self, head, node):
        if node.low <= head.high and node.high >= head.low:
            self.count += 1 
        print(self.count, head.high, head.low)        
        if head.left != None and head.left.highest >= node.low:
                return self._search(head.left, node)
        elif head.right != None:
                return self._search(head.right, node)       
        return self.count

data = input().split(" ")
N = int(data[0])
M = int(data[1])
intervals = interval()
for i in range(N):
    data = input().split(" ")
    p = node(int(data[0]), int(data[1]))
    intervals.add_node(p)
count = 0
for i in range(M):  
    data = input().split(" ")
    count += intervals.search(node(int(data[0]), int(data[1]))) 
print(count)

Answer 1

解决该问题的关键是要认识到没有必要将单个守备范围与单个射程进行比较，因为只需要知道相交范围的总数。为了在 O(n log n) 时间内实现这一点，可以使用以下算法。

获取拍摄范围并创建两个有序列表:一个用于起始值，另一个用于结束值。示例问题有镜头 [[1, 2], [2, 3], [4, 5], [6, 7]] 排序后我们有两个列表:[ 1, 2, 4, 6] 和 [2, 3, 5, 7]。到目前为止，一切都可以在 O(n log n) 时间内完成。

接下来处理外场球员。第一个玩家的范围是 [1, 5]。当我们使用起始值 1 对排序的结束值 [2, 3, 5, 7] 进行二进制搜索时，我们注意到所有射击范围都在起始值之后结束。接下来，我们使用结束值 5 对排序的起始值 [1, 2, 4, 6] 进行另一次搜索，我们注意到 3 射击范围开始在最终值之前或之后。然后我们通过简单的计算3 - 0 得出第一个外场球员可以与3 范围相交的结论。对所有外场球员 (M) 重复此操作需要 O(m log n) 时间。