使用区间树找出重叠区域

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) 时间。

Answer 2

我做了一些功课，尝试用区间 tree.But 来解决它，你已经意识到，传统的区间树可能不适合这个 problem.This 因为搜索时只返回一个匹配项一个区间树，但是我们需要精确地找到所有的matches.More，我们只需要计算所有的匹配，不需要找到所有的。

所以为了pruning.I我不熟悉python所以我在你的节点中添加了2个字段，在java中看起来像这样：

 static class Node implements Comparable<Node> {
    Node left;//left child
    Node right;//right child
    int low;//low of current node
    int high;//high of current node
    int lowest;//lowest of current subtree
    int highest;//highest of current subtree
    int nodeCount;//node count of current subtree

    @Override
    public int compareTo(Node o) {
        return low - o.low;
    }
}

为了做一棵平衡树，我把所有的区间排序，然后从中间向两边递归的建树（用红黑树可能更好），这对性能影响很大，所以我建议将此功能添加到您的程序中。

准备工作已经完成，far.The搜索方法如下所示：

  private static int search(Node node, int low, int high) {
    //pruning 1: interval [low,high] totally overlaps with subtree,thus overlaps with all children
    if (node.lowest >= low && node.highest <= high) {
        return node.nodeCount;
    }
    //pruning 2: interval [low,high] never overlaps with subtree
    if (node.highest < low || node.lowest > high) {
        return 0;
    }

    //can't judge,go through left and right child

    //overlapped with current node or not
    int c = (high < node.low || low > node.high ? 0 : 1);
    if (node.left != null) {
        c += search(node.left, low, high);
    }
    if (node.right != null) {
        c += search(node.right, low, high);
    }
    return c;
}

有 2 个主要修剪，因为当当前子树完全重叠或从不重叠时，注释 show.There 不需要遍历子树。

它在大多数情况下都运行良好，并已被接受 system.It 花费大约 4000 毫秒来解决最复杂的测试用例（N=99600，M=98000）。我仍在努力做更多优化，希望对你有帮助。

使用区间树找出重叠区域

Interval tree usage to find out overlapping regions

python

algorithm

tree