期間が重なっている回数のカウント方法

はじめに

稀によくある、期間の重複チェックのカウント方法。
予約の定員制限オーバーのチェックのときなどに。

データ

データは以下の感じで持っている想定。（イメージです。）

[
  {
    start: 2021/02/27 12:00,
    end  : 2021/02/27 13:30,
  },
  {
    start: 2021/02/27 12:30,
    end  : 2021/02/27 14:00,
  },
  {
    start: 2021/02/27 13:00,
    end  : 2021/02/27 14:30,
  },
]

単純な範囲チェック

以下のように単純にすべてのデータに対して重なっているデータ数をカウントしていったが、これは失敗だった。

let overlapCount: number[] = [periods.length]
for (let i = 0; i < periods.length; i++) {
  overlapCount[i] = 1;
  for (let j = 0; j < periods.length; j++) {
    if (i != j) {
      if (periods[j].start < periods[i].end && periods[i].start < periods[j].end) {
        overlapCount[i]++;
      }
    }
  }
}

以下のようなケースで、3と重なっている期間1,2があるため、合計3回とカウントされてしまったので。

範囲チェックでカウントするには、重なっている2つの期間を探し、さらにその両方と重なっている期間を探して・・・と再帰的に探す必要があり、かなり面倒そう。

開始と終了だけをカウントする

発想を変えて、期間を開始・終了混在の1次元配列に詰めて、時間順にソートし、startがあれば1インクリメント、endがあれば1デクリメントする方法を取った。
startが連続している回数がそのまま重なりの最大数になるはず、という発想。

最終的なソースは以下の通り。typescript。
これでうまくいった。はず。
注意点として、startとendが同じ時間の場合は先にendのほうを処理する（デクリメントする）必要があるので、endが上になるように並べること。
（下記では、先にendだけを配列に突っ込んでいる。）

    // create all time array
    let times = []
    for (let i = 0; i < periods.length; i++) {
      times.push({ date: periods[i].end,   type: "end" });
    }
    for (let i = 0; i < periods.length; i++) {
      times.push({ date: periods[i].start, type: "start" });
    }
    // sort by time
    times = times.sort((time1, time2) => {
      if (time1.date > time2.date) { return 1; }
      if (time1.date < time2.date) { return -1; }
      return 0;
    });

    // countup with start, count down with end
    let count = 0;
    let max = 0;
    for (let i = 0; i < times.length; i++) {
      if (times[i].type == "start") { count++; }
      if (times[i].type == "end")   { count--; }
      if (count > max) { max = count; }
    }
    return max;