☰

2つの範囲が重複しているかどうかをテストする最も効率的な方法は何ですか? 質問する

tag-icon • tag-icon performance range comparison
2つの範囲が重複しているかどうかをテストする最も効率的な方法は何ですか? 質問する

2 つの包含範囲 [x1:x2] と [y1:y2] (ただし、 および ) が与えられた場合、x1 ≤ x22y1 ≤ y2つの範囲に重複があるかどうかをテストする最も効率的な方法は何ですか?

簡単な実装は次のとおりです。

bool testOverlap(int x1, int x2, int y1, int y2) {
  return (x1 >= y1 && x1 <= y2) ||
         (x2 >= y1 && x2 <= y2) ||
         (y1 >= x1 && y1 <= x2) ||
         (y2 >= x1 && y2 <= x2);
}

しかし、これを計算するより効率的な方法があると思います。

操作が最も少なくなるという点で最も効率的な方法は何でしょうか?

ベストアンサー1

範囲が重なるということはどういう意味でしょうか？それは、両方の範囲に含まれる数値Cが存在することを意味します。つまり、

x_start <= C <= x_end

そして

y_start <= C <= y_end

混乱を避けるために、範囲は次のようになります[x_start:x_end]。[y_start:y_end]

さて、範囲が整形式であると仮定できる場合（つまり、x_start <= x_endおよびy_start <= y_end）は、次のことをテストするだけで十分である。

x_start <= y_end && y_start <= x_end

おすすめ記事