기간이 겹치는 횟수를 계산하는 방법

소개

드물게 자주 있는, 기간 중복 체크의 계산 방법.
예약의 정원 제한 오버 체크시 등에.

데이터

데이터는 이하의 느낌으로 가지고 있다고 가정. (이미지입니다.)

[
  {
    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;