📏

端点が無限の場合も考慮した、区間に関するあれこれ

2022/11/18に公開

TypeScript

アルゴリズム

tech

概要

[begin, end] をPeriod型とする
intersectionとか取ろうとすると毎回悩む
両端が有限の時だけでなく、±∞の時も扱いたい

Period型

期間・区間を表す型で、以下のようなものを考えます
私は期間の話でコードを書いていたのでDateですが、数値に置き換えてもロジックは同じだと思います

class Period {
    begin?: Date
    end?: Date
}

ここで、 undefined の場合は無限小・無限大を表すものとします

// 現在以降ずっと
new Period(new Date(), undefined)

// 現在までずっと
new Period(undefined, new Date())

// これまでも、これからも
new Period(undefined, undefined)

シンプルに有限区間の場合は色々シンプルで、例えば $[a, b], [c, d]$ が共通部分を持つかの判定は $a<d \land b<c$ で表すことができます

今回は開いた区間も考慮するのですが、あまり記事等も見つからなかったのでまとめました

ある時刻を含むかどうか

コーナーケースはお好みで

/**
 * 期間がある時刻を含むかどうか
 * periodの左端は含むが右端は含まない [)
 * @param period
 * @param datetime
 */
export const periodIncludes = (period: Period, datetime: Date): boolean =>  {
    return (!period.begin || period.begin <= datetime)
        && (!period.end || datetime < period.end)
}

2つの期間の共通部分があるかどうか

これは余事象を考えるといいです
これもコーナーケースはお好みで

/**
 * 二つの期間に共通部分があるかどうか
 * 共通部分が1点の時はfalse
 * @param a
 * @param b
 */
export const hasIntersection = (a: Period, b: Period): boolean => {
    const { begin: xb, end: xe } = a
    const { begin: yb, end: ye } = b

    // 余事象をとると、片方が左、片方が右にあって被っていない時になる
    return !((xb && ye && ye <= xb) || (xe && yb && xe <= yb))
}

2つの期間の共通部分

共通部分があるとして、begin候補/end候補をそれぞれ考えると楽です

/** Period-AとPeriod-Bに対し、(Period-A) ∧ (Period-B) を返す。
 * 共通部分が1点の時はnullとする
 * **/
export const getIntersection = (a: Period, b: Period): Nullable<Period> => {
    const { begin: xb, end: xe } = a
    const { begin: yb, end: ye } = b

    if (!hasIntersection(a, b)) return null // 枝刈り

    const l = xb ? (yb ? (xb < yb ? yb : xb) : xb) : yb // 左側候補はmaxで
    const r = xe ? (ye ? (xe < ye ? xe : ye) : xe) : ye // 右側候補はminで

    const obj: IPeriod = {}
    if (l) obj.begin = l
    if (r) obj.end = r
    return new Period(obj) // hasIntersectionがtrueなので l < r は担保されている
}

一方の期間を、他方の期間で削る

Period-Aのうち、Period-Bに属さない部分を得たい場合です
これも、左側候補と右側候補をそれぞれ考えれば良いです

/** Period-AとPeriod-Bに対し、(Period-A) ∧ ¬(Period-B) を返す。
 * 生き残るとすればfilterの左右のたかだか2区間しかないので、それぞれ計算している
 * **/
export const cutOutPeriod = (target: Period, filter: Period): Period[] => { 
    const output = []
    if (filter.begin) {  // 左側が生き残るとしたら
        const l = getIntersection(target, new Period({end: filter.begin}))
        if (l) output.push(l)
    }
    if (filter.endDatetime) {  // 右側が生き残るとしたら
        const r = getIntersection(target, new Period({begin: filter.end}))
        if (r) output.push(r)
    }
    return output
}

まとめ

業務コードとして書いたので可読性を重視したが、計算量・コード量を詰めるならもっとシンプルにできるかも