使用区间树查找重叠区域

Question

使用区间树查找重叠区域

4

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

将要举行一场板球比赛。该场地由一个一维平面表示。一个名叫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)

- noman pouigt

有一种比区间树更简单的解决方案，只需要排序和二分查找。试着想一想，如果你能查询有多少射击范围在守备范围结束之前开始，以及有多少射击范围在守备范围开始之后结束，会怎样呢？ - niemmi

@niemmi：由于即使下限较低，上限仍可能拥有整个字段，因此它几乎会像0（n）一样糟糕。 - noman pouigt

没错，它比O(n)更糟糕。确切地说，它是O(n log n + m log n)，其中n是射击次数，m是玩家数量。但它仍然足够快以通过所有测试用例。 - niemmi

@niemmi: 我不明白为什么您要对单人搜索使用对数(log(n))。如果您可以用一个示例来发布您的答案，那将很好，我会标记它为正确答案。 - noman pouigt

2个回答

0

我做了一些功课，尝试使用区间树来解决这个问题。但是正如你所意识到的那样，传统的区间树可能不适用于此问题。这是因为在搜索区间树时只返回一个匹配项，但我们需要找到所有匹配项。更确切地说，我们只需要计算所有匹配项的数量，而不需要找到它们全部。

因此，我为了剪枝，在您的节点中添加了2个字段。我不熟悉Python，在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;
    }
}

为了构建一棵平衡树，我会先对所有区间进行排序，然后从中间开始递归地向两侧构建树（最好使用红黑树）。这对性能影响很大，因此我建议将此功能添加到您的程序中。

目前准备工作已经完成。搜索方法如下：

  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;
}

根据注释，有两种主要的修剪方式。当当前子树完全重叠或从未重叠时，无需遍历其子节点。

它在大多数情况下都能很好地工作，并已被系统接受。解决最复杂的测试用例（N=99600，M=98000）大约需要4000毫秒。我仍在尝试更多的优化，希望能有所帮助。

- kensou97

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- niemmi · Accepted Answer

解决问题的关键在于意识到无需将单个防守范围与单个射击范围进行比较，因为只需要知道相交范围的总数。为了在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)的时间。