はじめに
ちょっと重い記事が続いてたので今回は小ネタです。
二つの区間データ、要するに数値の区間であれば最小値と最大値のペア、時刻の区間であれば開始時間と終了時間のデータが二つあったときに、それらの区間に重複があるかどうかをサクッと判定するアルゴリズムを紹介します。昔どこかでみた覚えがあるのですが、久々に実装で必要になったときにちょっとだけ悩んだのでそのメモです。
結論
結果だけ知りたい人向けに先に結論だけ書いときます。
区間[s1, e1]と[s2, e2]に重複があるかどうかは次の2つの方法で判定できます。
方法1: $(s1 \leq e2) \land (s2 \leq e1)$ ならばその2区間には重複があります。
方法2: $\max(s1, s2) \leq \max(e1, e2)$ ならばその2区間には重複があります。
両方の方法のメリットデメリットですが、方法1の方が計算速度が速いです。大小比較2個と論理演算ですからmax関数呼び出すより有利ですね。ただ、方法2の方は、応用として、二つの区間に重複があった場合、$\max(e1, e2) – \max(s1, s2)$で重複区間の長さを算出できます。(値が負になったら重複無し。)
(max関数がそんな極端に遅いってこともなく、わざわざ時間測定しない限り体感することもない速度差ではあるのであくまでも参考にどうぞ。)
方法1の導出
これだけで終えてしまうと記事量としてあまりに少ないのと、結論だけ書いてるとすぐ忘れそうなので、真面目に導出を説明しておきます。まずは方法1の方からです。
まず、二つの区間の相対的な位置関係は次の6パターンが存在します。(説明の単純化のため。s1,s2,e1,e2は全て異なる値とします。)
- 区間1全体が区間2より小さい。つまり、 $s1 < e1 < s2 < e2$.
- 区間1全体が区間2より大きい。つまり、 $s2 < e2 < s1 < e1$.
- 区間1が区間2に内包される。つまり、$s2 < s1 < e1 < e2$.
- 区間1が区間2を内包する。つまり、$s1 < s2 < e2 < e1$.
- 区間1の後半と区間2の前半が重なる。つまり、$s1 < s2 < e1 < e2$.
- 区間1の前半と区間2の後半が重なる。つまり、$s2 < s1 < e2 < e1$.
上記の6パターンのうち、1,2 が区間に重複がなく、3,4,5,6は区間に重複があります。
ここで、「そうか！3,4,5,6のどれかを満たすことを確認すればいいんだ！」と判断して4パターンの論理式を書いてorで繋ぐ、としないことがコツです。
区間に重複がないパターンの方が2種類しかなくて判定が単純なんですよね。そして、区間の定義から$s1<e1$と$s2<e2$はわかってるので、あと確認するのはe1とs2, e2とs1の代償関係だけなんですよ。
ということで、 $(e1 < s2) \lor (e2 < s1)$ であれば二つの区間に重複はないと言えます。
これの否定を考えると、ドモルガンの法則から方法1としてあげた式が導かれます。
方法2の導出
続いて方法2の導出です。
これは、先ほど挙げた3,4,5,6の4パターンの不等式を眺めると見つかる法則性なのですが、左の2辺はs1,かs2で、右の2辺はe1, e2なんですよね。
これを素直に数式に落とすと、$\max(s1, s2) \leq \max(e1, e2)$ となります。等号が成立するのはただ1点だけが重複する場合。
そして、区間が重複する場合は、$\max(s1, s2)$は重複区間の開始点であり、$\max(e1, e2)$は重複区間の終了点なので、この2項の差を取ると重複部分の長さも得られます。
まとめ
そんなに難しい計算ではなく、覚えてさえればサクッと実装できる式ではありますが、重複のパターンって4種類あるよなぁと考え始めてしまうと意外に手間取ります。
結果を丸暗記しなくても、区間が重複しないパターンは2個しかなくてそれを否定したら簡単だってことを頭の片隅にでも置いといてもらえると幸いです。