あったこといろいろ

ほぼ自分用備忘録です。

プログラミングにおける「半開区間」

はじめに

プログラム中では、区間は 閉区間 や 半開区間 など様々な方法で扱うことができます。
僕は閉区間派でしたが、最近半開区間派に鞍替えしました。
これにあたって半開区間の特徴をまとめたのが本記事です。

大したことは書かれていないので、半開区間の ①区間の長さ ②区間の分割方法 ③区間の包含判定 ④区間の交差判定 ⑤区間の隣接判定 がパッと書ける人にとっては無用な記事となっています。

※なおここでは整数値によって表現される区間を対象とします。

半開区間とは

[a,b)で表される区間を左閉右開区間(左閉半開区間)と言い、
(a,b]で表される区間を左開右閉区間(右閉半開区間)と言います。
これらを合わせて半開区間と呼びます。
※角括弧と丸括弧の意味の違いの説明はここでは省略します

この記事では、競技プログラミングにおいてもよく利用されている[a,b)(左閉右開区間)について扱います。

記号の定義

本記事では区間(segment)を {S} と表し、添字は識別子を表します。
区間の情報は [l,r) で表し、区間 {S_i} の情報は [{l_i, r_i}) です。

特徴

区間の長さ

区間 {S} の長さは r - l と等しくなります。

区間の分割

区間 [l,r) を、c-1とcの間を境界として分割すると、[l,c) と [c,r) の2つの区間ができます。
(閉区間で同様の事を行うと、[l,r-1] -> [l,c-1]と[c,r-1] となり少しややこしいです。)
f:id:Yazaten:20170519214614p:plain


区間の包含関係

{ l_1 \leq l_2 } かつ { r2 \leq r_1 }のとき、{S_2}{S_1}に包含されています。

区間の交差判定

{ l_1 \leq l_2 < r_1 } または {l_2 \leq l_1 < r_2 } のとき、{S_1}{S_2} は交差しています。

ある2区間 {S_1}{S_2} が隣接しているかの判定

{ l_1 = r_2 } または { l_2 = r_1 } のとき、{S_1}{S_2} は隣接しています。


まとめ

半開区間は、区間の長さを調べたり区間を分割するときに便利です。
二分探索でも多くの場合半開区間を用いているので、このあたりをおさらいしておくと何かの役に立つかもしれません。