はむはむエンジニアぶろぐ

365日エンジニアリング

2つの期間で重なる期間が存在するか判定するアルゴリズム

この記事はアルゴリズム Advent Calendar 2015 - Qiita 7日目の記事です。
担当は@secret_hamuhamu です。

私は、理系出身の人間ではなく数学もほとんどできないので、論理的に数学的に説明できていないと思います。
ですが、このような説明の仕方のほうが、わかりやすいよみたいなご指摘があれば是非コメントにでも書いていただけると幸いです。

やりたいことの説明

こちらの図を御覧ください。
f:id:secret_hamuhamu:20151205183800p:plain

矢印を期間だと思ってください。

青色の矢印と重なる期間がなければ
青色の矢印と重なる期間があれば

ということを判定したいと思います。
オレンジ色の矢印が、緑色の矢印が、です。

予約システム等で使われる条件だと思います。
Xさんは、Aルームを2015年12月01日 ~ 2015年12月05日まで予約する。
他の人はAルームを、2015年12月01日 ~ 2015年12月05日の間、予約することが出来ない。

こちらのブログのタイトルと内容が被ってますが、本記事を書いている途中で見つけました。
2つの期間が重なり合うかどうかを判定する。

PHPで実装してみた

PHPで実装してみました。
PHP読めなくても多分読めるはず。

<?php

class TermTest extends PHPUnit_Framework_TestCase
{
    public function dp_2つの期間で重なる期間が存在しない()
    {
        return [
            [new DateTime('2015-11-27 00:00:00'), new DateTime('2015-11-30 23:59:59'), true],   // A
            [new DateTime('2015-12-06 00:00:00'), new DateTime('2015-12-08 23:59:59'), true],   // B
            [new DateTime('2015-12-02 00:00:00'), new DateTime('2015-12-04 23:59:59'), false],  // C
            [new DateTime('2015-11-27 00:00:00'), new DateTime('2015-12-08 23:59:59'), false],  // D
            [new DateTime('2015-11-27 00:00:00'), new DateTime('2015-12-02 23:59:59'), false],  // E
            [new DateTime('2015-12-04 00:00:00'), new DateTime('2015-12-08 23:59:59'), false],  // F
        ];
    }

    /**
     * @test
     * @dataProvider dp_2つの期間で重なる期間が存在しない
     * @param DateTime $yStartDt Y始点
     * @param DateTime $yEndDt   Y終点
     * @param boolean $expected  存在しなければtrue/存在すればfalse
     *
     */
    public function 2つの期間で重なる期間が存在しない($yStartDt, $yEndDt, $expected)
    {
        $xStartDt = new DateTime('2015-12-01 00:00:00');  // X始点
        $xEndDt   = new DateTime('2015-12-05 23:59:59');  // X終点

        $notExist = $yEndDt < $xStartDt || $xEndDt < $yStartDt;

        $this->assertSame($expected, $notExist);
    }
}

DateTimeというオブジェクトを使ってますが、日付の比較を簡単にするために使っているだけです。

PHPでやってることは、以下のテーブルの内容で期待値通りかテストしているだけです。

始点 終点 期待値
X 2015-12-01 00:00:00 2015-12-05 23:59:59 -
A 2015-11-27 00:00:00 2015-11-30 23:59:59
B 2015-12-06 00:00:00 2015-12-08 23:59:59
C 2015-12-02 00:00:00 2015-12-04 23:59:59
D 2015-11-27 00:00:00 2015-12-08 23:59:59
E 2015-11-27 00:00:00 2015-12-02 23:59:59
F 2015-12-04 00:00:00 2015-12-08 23:59:59

A ~ Fの総称をYとします。

Yの終点が、Xの始点未満である 又は Xの終点が、Yの始点未満であれば真となります。

Yの終点 < Xの始点 || Xの終点 < Yの始点


逆に、2つの期間で重なる期間が存在する場合、真としたければ式を反転するだけでよい。(当たり前だけど)

!(Yの終点 < Xの始点 || Xの終点 < Yの始点)