☰

2 つの範囲の重複部分を見つけるにはどうすればよいですか? [closed] 質問する

tag-icon • tag-icon java
2 つの範囲の重複部分を見つけるにはどうすればよいですか? [closed] 質問する

2 つの範囲の重なりを見つける効果的な方法はありますか?

考えられるすべてのケース

実際には、2 つの範囲は (a - c) と (b - d) としてマークされており、(c > a) && (d > b) であると想定します。

(b <= a <= d) which means if ((a >= b) && (d > a))
(b <= c <= d) which means if ((c >= b) && (d >= c))
(a <= b <= c) which means if ((b > a) && (c > b))
(a <= d <= c) which means if ((d > a) && (c > d))

しかし、この方法では一度に 1 つの範囲しか見つけられず、各範囲で他のケースも確認する必要があるため、終わりはありません。

たとえば、最初の条件 (1) が正しければ、範囲の開始 (a) で何が起こっているかがわかりますが、範囲の終了 (c) については他の条件を確認する必要があります。

言うまでもなく、これはすべて (c > a) && (d > b) の場合に機能し、いずれかが他のものと等しくありません。

ベストアンサー1

2 つの範囲は、次の 2 つの基本的なケースのいずれかで重複します。

  • 一方の範囲が他方の範囲を完全に包含している（つまり、一方の範囲の開始と終了の両方が、他方の範囲の開始と終了の間にある）、または
  • 一方の範囲の開始または終了が他の範囲に含まれる

逆に言えば、ない各範囲のどちらの端点も他の範囲に含まれていない場合にのみ重複します (図のケース 11 と 12)。どちらかの範囲の下限がもう一方の上限を超えているかどうかをチェックして、両方のケースを検出できます。

if (a > d || c < b) {
    // no overlap
}
else {
    // overlap
}

条件を逆転させて、ド・モルガンの法則を使用して順序を入れ替えることもできます。

if (a <= d && c >= b) {
    // overlap
}
else {
    // no overlap
}

実際の重複範囲を見つけるには、2 つの下限値の最大値と、2 つの上限値の最小値を取得します。

int e = Math.max(a,b);
int f = Math.min(c,d);
// overlapping range is [e,f], and overlap exists if e <= f.

上記はすべて、範囲が包括的つまり、 と によって定義される範囲にはa、cの値aと の値の両方が含まれますc。ただし、排他的範囲を調整するのはかなり簡単です。

おすすめ記事