3

間隔の重複がない場合は実装する必要があります。

インターバルは次のようになります。

0-100
100-200
200-500
500-1000
1000-2000 ect....

現在、区間はmin（0,100,200,500 ...）とmax（100,200,500 ...）の配列リストに別々に格納されています。

新しいインターバルを追加する場合、既存のインターバルと重複していないかどうかを確認する必要があります。元。：

250-280は大丈夫です300-600は大丈夫ではありません

しかし、私はそれをどのように行うのか分かりませんか？

4

7 に答える 7

5

このタスクには区間木データ構造を使用でき、区間に衝突/交差がない場合にのみ要素を追加できます。

于 2012-11-10T15:54:42.017 に答える
1

区間（a、b）の場合

1リストをループする

2いずれかaの間隔内にある場合、間隔は重複しています。

a32つの間隔がどの間にあるかを見つけます

4で繰り返しbます。ここでも、bが任意の間隔内にある場合、それはオーバーラップします。

5aとbが2つの同じ間隔の間にある場合、それらはオーバーラップしません。それ以外の場合、それらは重複します。

そしてもちろん、アルゴリズムを開始する前に、間隔をオブジェクトとして管理する単一の配列リストを使用するというYobのアドバイスを行うことをお勧めします。

于 2012-11-10T15:51:57.707 に答える
1

現在、区間はmin（0,100,200,500 ...）とmax（100,200,500 ...）の配列リストに別々に格納されています。

それで ...

bool isCollided = false;
Integer min = 250;
Integer max = 280;
for(Integer intOne: firstList){
  Integer intTwo = secondList.get(firstList.indexOf())
  if( (min >= intOne && <= intTwo) || (max >= intOne && <= intTwo){
    isCollided = true;
    break;
  }
}

しかし、他の人が提案したように、私はおそらく自分のクラスを作成するでしょう。

于 2012-11-10T15:58:30.563 に答える
0

NavigableMapなどの開始点で並べ替えることができます。

NavigableMap<Integer, Integer> map =
map.put(100, 200);
map.put(300, 500);

// to test for a range.
int start = 300, end = 400;
if (map.floorEntry(start).getValue() >= start && map.ceilingKey(start) <= end)
   // out of existing ranges.

この操作はO（ln N）です。

于 2012-11-10T20:21:36.607 に答える
0

おそらく、ArrayListに配置する開始と終了を含むIntervalオブジェクトを作成しました。

衝突を検出できるこのクラスのメソッドを簡単に実装できます。

public boolean hasCollision(Interval inter){....}

ここで、挿入する前に、コレクションを反復処理してhasCollision（）メソッドを呼び出します...結果を最適化したい場合は、Intervalオブジェクトを実装ComparableしてSortedコレクションを使用することもできます。

于 2012-11-10T15:50:40.407 に答える
0

間隔は重複しないため、たとえば下限で並べ替えておくことができます。指定された間隔が既存の間隔と重複しているかどうかを確認するには、バイナリ検索を使用できます。この方法では、検索時間はlog（N）になります。

class Interval implements Comparable<Interval>を作成して使用することをお勧めしますjava.util.TreeMap<Integer, Interval>。重要なのは、下限と上限の合計です。newを挿入するときInterval iは、次の2つのエントリのみと重複していることを確認してください：map.floorEntry(i.key())とmap.lowerEntry(i.key())。

于 2012-11-10T16:37:19.987 に答える
0

ユーティリティメソッドとして簡単なメソッドがあります

public static boolean isOverlapping（Date start1、Date end1、Date start2、Date end2）{return start1.before（end2）&& start2.before（end1）; }

于 2014-01-16T22:04:35.103 に答える