algorithm - 複数の区間の重なりを見つける

Question

間隔（または範囲）のリストがあるとしましょう（例：10-15、5-7、9-12 ..）。問題は、重複する範囲のサブセットを見つけることです。もちろん、これにはインターバルツリーを使用できます。

私が抱えている実際の問題は、複数の範囲があることです。例によって最もよく説明されています：

1. 10-15、5-7、9-12
2. 1-2、3-6、14-15
3. 3-5、9-15、10-15

上記の場合、第 2 範囲では (1) と (2) が重複し、第 3 範囲では (3) と (1)、(2) が重複しています。

基本的に、アイテムのリスト間の重複をすべて見つける必要があります。

たぶん、これを見つけるために 3 つの別々のインターバル ツリーを使用できます。これを行うより良い方法はありますか？

Answer 1

すべてのインターバルを含むインターバル ツリーを 1 つだけ作成できます。次のように、間隔がどの範囲に属していたかを追跡する必要があります。

{
  int range;
  int intervalFrom;
  int intervalTo;
}

その構造を間隔ツリー内に配置して、重複をチェックできます。問題のある間隔を取得すると、それぞれがどの範囲に属しているかがわかります。

Answer 2

区間 [a0, b0] と [a1, b1] は、min(b1,b0) > max(a1,a0) の場合に重複します