2つの区間（Range）の重複を判定する方法

どうも、「病院なび」の開発チームメンバー甘利です。
今日は区間（Rangeクラス）の重なりの判定について説明します。

Rangeクラスを利用していると、それらが重なっているか？という判定をしたくなる時があります。
ActiveSupportを利用していれば .cover? メソッドを利用することができますが、
そうじゃない時はどうしたら良いでしょうか。

ふたつの閉区間を表すRangeオブジェクトの r1 と r2 があり、
r1, r2 の端をそれぞれ　r１_s, r1_e、r２_s r2_e　と表すとします。
さて、このふたつのRangeが重なっていることを判別するにはどうしたら良いでしょうか。

順当に考えてみる

ふたつのRangeの区間が重なっているとはどういうことかを書き出してみますと、
以下のいずれかが成り立つとき、とうことになります。

1. r1 の範囲に r２_s が含まれている
2. r1 の範囲に r２_e が含まれている
3. r2 の範囲に r1_s が含まれている
4. r2 の範囲に r1_e が含まれている

これをRubyのコードでそのまま書くとこうなります。

 r1.include?　r2.min ||
 r1.include?　r2.max ||
 r2.include?　r1.min ||
 r2.include?　r1.min 

うーん、これは書きたくないですね。

重なっていない状態を考えてみる。

考え方を少し変えてみます。重なっているときの条件ではなく、重なっていない時の条件を書き出し、
それを否定するという方法です。
重なっていない時の条件は以下のいずれかの時です。

1. r1_e よりも r2_s が大きい
2. r2_e よりも r1_s が大きい

これをRubyのコードでそのまま書くとこうなります。

 r1.max　< r2.min || r2.max　<　r1.min

つまり、重なっていない時はその逆なので

 ！（r1.max　< r2.min || r2.max　<　r1.min）

で、それをド・モルガン使って書き換えます。
https://ja.wikipedia.org/wiki/%E3%83%89%E3%83%BB%E3%83%A2%E3%83%AB%E3%82%AC%E3%83%B3%E3%81%AE%E6%B3%95%E5%89%87

　　　　　　　　!(r1.max　< r2.min　||　r2.max　<　r1.min)
　→ !(r1.max　< r2.min) && !(r2.max　<　r1.min)
　→ 　　　　r1.max　>= r2.min && r2.max　>=　r1.min

となります。これで完璧です！！！

試しに使ってみる。

上記のロジックをkasanaru?メソッドとして実装して試してみます。
(巷にあるメソッドと区別がつく様にあえて日本語、ローマ字表記で命名しています。)

irb(main):001:1* def kasanaru?(range1, range2)
irb(main):002:1*   range1.end >= range2.begin && range2.end >= range1.begin
irb(main):003:0> end
=> :kasanaru?
irb(main):004:0> kasanaru? (1..3), (4..6) 
=> false
irb(main):005:0> kasanaru? (1..3), (2..5) 
=> true
irb(main):006:0> kasanaru? (1..10), (2..5) 
=> true
irb(main):007:0> kasanaru? (3..4), (2..5) 
=> true
irb(main):008:0> kasanaru? (3..8), (1..4) 
=> true

いい感じです。

irb(main):009:0> kasanaru? (3..), (..4) 
(irb):2:in `kasanaru?': undefined method `>=' for nil:NilClass (NoMethodError)
        from (irb):9:in `<main>'                                                         
        from /usr/local/lib/ruby/gems/3.1.0/gems/irb-1.4.1/exe/irb:11:in `<top (required)>'
        from /usr/local/bin/irb:25:in `load'                                             
        from /usr/local/bin/irb:25:in `<main>'                                           
irb(main):010:0> 

(┐「ε:)_ｽﾞｺｰ、　調子のったらこれです。

Beginless or Endress Range

RubyのRangeでは以下の様に始点、および終点を定義しない区間が定義できます。
以下はどちらも有効なRangeのリテラル表記です。

(..1)
(3..)

他の言語では最大値をつかって表現するのですが、Rubyではnilを端の値にすることで最大値を表現しています。
そのため、これらのRangeオブジェクトを先ほどのkasanaru?メソッドに与えると、nilとの比較が発生し、うまく動作しません。

これらも考慮するともう少し複雑な判定式を用意しないといけません（考えたくない。）

まとめ

ということでまとめです。　両端のあるRangeオブジェクトどうしで、
区間が被っているかどうかを判定する時は以下の通りで良いと思います。

r1.max　>= r2.min && r2.max　>=　r1.min

begin or end less な区間なんて知りません。

以上です。
もし今回の記事が少しでも面白いと思った方は、LGTMをお願いします。
記事に対する鉞は叩き落としますが、マシュマロは大好物です。