자바스크립트로 겹치는 시간 구간 확인하기

시작 시간과 종료 시간을 담고 있는 구간(interval) 객체의 배열이 주어졌을 때, 그중 서로 겹치는 시간대가 있는지 확인하는 자바스크립트 함수를 작성해 보겠습니다. 입력 데이터는 다음과 같은 형태입니다.

const arr = [
  { start: '01:00', end: '04:00' },
  { start: '05:00', end: '08:00' },
  { start: '07:00', end: '11:00' },
  { start: '09:30', end: '18:00' },
];

문제 요건

함수는 이 객체 배열을 순회하면서 각 요소를 나머지 요소들과 하나씩 비교해야 합니다. 겹치는 구간을 발견하는 즉시 반복을 중단하고 true를 반환하고, 끝까지 겹치는 구간이 없다면 false를 반환합니다.

여기서 말하는 겹치는 구간(overlapping intervals)이란 두 시간 구간이 공통으로 포함하는 시간이 일부라도 존재하는 경우를 의미합니다.

구현 방법

핵심 로직은 두 단계로 나눌 수 있습니다. 첫째, '01:00'처럼 'HH:MM' 형식의 시간 문자열을 자정부터 경과한 총 분(minute) 수로 변환합니다. 둘째, 두 구간이 겹치는 조건은 'a.end가 b.start보다 크고, b.end가 a.start보다 클 때'라는 간단한 부등식으로 표현됩니다.

const arr = [
  { start: '01:00', end: '04:00' },
  { start: '05:00', end: '08:00' },
  { start: '07:00', end: '11:00' },
  { start: '09:30', end: '18:00' },
];

// 두 구간이 겹치는지 검사하는 함수
const overlapping = (a, b) => {
  const getMinutes = s => {
    const p = s.split(':').map(Number);
    return p[0] * 60 + p[1];
  };
  return getMinutes(a.end) > getMinutes(b.start)
      && getMinutes(b.end) > getMinutes(a.start);
};

// 배열 전체에서 겹치는 구간이 하나라도 있는지 확인
const isOverlapping = (arr) => {
  let i, j;
  for (i = 0; i < arr.length - 1; i++) {
    for (j = i + 1; j < arr.length; j++) {
      if (overlapping(arr[i], arr[j])) {
        return true;
      }
    }
  }
  return false;
};

console.log(isOverlapping(arr));

동작 원리 살펴보기

getMinutes 함수는 시간 문자열을 콜론(:) 기준으로 분리한 뒤, 시(hour)에 60을 곱하고 분(minute)을 더해 총 분 수로 바꿉니다. 예를 들어 '09:30'은 9 × 60 + 30 = 570이 됩니다. 문자열끼리 직접 비교하는 것보다 숫자로 변환해 비교하는 편이 훨씬 안전하고 명확합니다.

두 구간 [a.start, a.end]와 [b.start, b.end]가 겹치려면, 한쪽의 끝이 다른 쪽의 시작보다 늦으면서 동시에 반대쪽 끝도 상대의 시작보다 늦어야 합니다. 조건을 양방향으로 모두 검사하기 때문에 한쪽만 비교할 때 발생할 수 있는 잘못된 판정을 막을 수 있습니다.

위 예제에서는 '07:00~11:00' 구간이 '05:00~08:00' 구간과 겹치므로 결과는 다음과 같습니다.

실행 결과

true

참고로 이 알고리즘은 모든 구간 쌍을 비교하므로 시간 복잡도는 O(n²)입니다. 구간 개수가 매우 많다면 시작 시간을 기준으로 먼저 정렬한 후 인접한 구간끼리만 비교하면 O(n log n)까지 성능을 개선할 수 있습니다.