オーバーラップ領域を見つけるためのインターバルツリーの使用

Question

これを解決するためにインターバルツリーを使用しようとしています。problem。以下は私の試行ですが、それは動作していない、つまり、すべての間隔を返すわけではありません。

クリケットの試合が行われる予定です。フィールドは1D平面で表されます。クリケット選手、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）時間で達成するために、以下のアルゴリズムを用いることができる。

ショット範囲を取得し、開始値と終了値の2つの順序付きリストを作成します。問題の例は[[1, 2], [2, 3], [4, 5], [6, 7]]であり、ソート後には[1, 2, 4, 6]と[2, 3, 5, 7]という2つのリストがあります。これまでのことはすべてO（n log n）時間で行うことができます。

次の処理は外野選手です。最初のプレーヤーの範囲は[1, 5]です。開始値1をソートされた終了値にバイナリ検索すると、[2, 3, 5, 7]はすべてのショット範囲が開始値の後で終了することに気付きます。次に、最終値5とソートされた開始値の別の検索を行います。[1, 2, 4, 6]3のショット範囲が開始値または終了値で開始することがわかります。次に、最初の外野選手が3の範囲を横切ることができると結論付けるために、単純な計算3 - 0を実行します。すべての外野選手（M）にこれを繰り返すと、O（m log n）時間がかかります。

Answer 2

私はいくつかの宿題を行い、インターバルツリーで解決しようとしました。しかし、あなたが理解したように、従来のインターバルツリーはこの問題には適していないかもしれません。これはインターバルツリーを検索するときに1つの一致すべての試合を見つける必要があります。正確には、すべての試合を数えるだけで、すべてを見つける必要はありません。

は、だから私は、Pythonに精通していないpruning.I'mのために自分のノードに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; 
    } 
} 

バランスの取れたツリーを作るためには、Iソートすべての間隔を取得し、再帰的に中央から両側にツリーを構築します（赤黒のツリーを使用する方が良いかもしれません）。これはパフォーマンスに大きな影響を与えるため、この機能をプログラムに追加することをお勧めします。

準備が完了しているので、far.The検索方法は次のようになります。コメントとして2つの主な剪定がありshow.Thereは、現在のサブツリーがあるときに子供を経由する必要はありませんです

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）を解決するには約4000msのコストがかかります。さらに最適化を行いたい役に立った