範囲が重なっているかどうかの判定法

直線上に2つの範囲AとBがあったとき、この2つが少しでも重なっているかどうかを調べたいときってありますよね。ありますよね？

例えば、1:00-2:00のような時間帯の情報があるとして、2つの時間帯AとBが重なっているかどうかを調べたい場合。
Aが1:00-2:00、Bが1:30-2:30だったら重なっている、Bが2:10-2:40なら重なっていない…といった具合です。

重なっている例
       01:00    01:30    02:00    02:30
         |        |        |        |
A        <----------------->        |
B        |        <----------------->

重なっていない例
       01:00    01:30    02:00    02:30
         |        |        |        |
A        <----------------->        |
B        |        |        |  <------->

この「重なっているか否か」を判断する方法について解説します。

これからドヤ顔で解説しますが、別に本邦初公開でも何でもありません。
「そんなもん知っとるわボケ」と思っても優しく見守ってください。

準備

まず、「範囲」を示す型を準備します。ここではTypeScriptのinterfaceを使いますが、C言語の構造体のようなものだと思ってください。

interface Range {
    begin: number;
    end: number;
}

とりあえずbegin≦endだと仮定しておきます。

次に「重なっている」の定義です。 上で1つだけ重なっている例を挙げましたが、全部でこの4種類があります。

Aが先
A        <----------------->
B                 <----------------->

Bが先
A                 <----------------->
B        <----------------->

AがBを包含
A        <--------------------->
B              <--------->

BがAを包含
A              <--------->
B        <--------------------->

コード

では実際のコードです。
先程の4つのケースをすべて網羅するとこんな感じ？とりあえず境界が一致している場合のような細かいケースは考えず、大まかなロジックだけ見てください。

interface Range {
    begin: number;
    end: number;
}

function overlapped(a: Range, b: Range): boolean {
    if (a.begin < b.begin && a.end > b.begin && a.end < b.end) {
        // Aが先
        return true;
    }
    if (b.begin < a.begin && b.end > a.begin && b.end < a.end) {
        // Bが先
        return true;
    }
    if (a.begin < b.begin && a.end > b.end) {
        // AがBを包含
        return true;
    }
    if (b.begin < a.begin && b.end > a.end) {
        // BがAを包含
        return true;
    }

    // どれでもなければ重なっていない
    return false;
}

なんかややこしいですね。もうちょっと簡単にできないでしょうか。

こうしましょう

もっと簡単に判定できる方法があります。

interface Range {
    begin: number;
    end: number;
}

function overlapped(a: Range, b: Range): boolean {
    if (a.end < b.begin) {
        // 重なっていない
        return false;
    }
    if (b.end < a.begin) {
        // 重なっていない
        return false;
    }

    // どちらでもなければ重なっている
    return true;
}

これだけです。
一応解説をしますが、逆転の発想ですね。重なっていない場合を考えます。

重なっている場合はいろいろ面倒なのに対して、重なっていない場合はこの2通りだけです。

Aが先
A        <------>
B                <------>

Bが先
A                <------>
B        <------>

そして最初にbegin≦endという前提条件をつけておいたので、純粋に「a.endとb.begin」、「b.endとa.begin」の2つを比較するだけで済みます。

何かのときに役に立つかも知れませんので覚えておいてください。