2406. Divide Intervals Into Minimum Number of Groups

~~이걸 어떻게 바로 생각해내서 풀 수 있는건가요?~~

필요한 최소 그룹 수는 특정 지점에서 겹치는 구간들의 최대 수와 동일하다. 구간을 일일이 탐색하는 것은 시간 초과일 수 밖에 없기 때문에 다른 방법을 생각해내야 했다. (그리고 도저히 생각나지 않아서 클로드의 가이드를 참고했다...)

구간의 시작과 끝을 각각 구간에 입장하는 이벤트와 퇴장하는 이벤트라고 생각해보자. 구간이 [1,3]이라면 1에서 입장(+1)하고 3에서 퇴장(-1)하는 이벤트가 발생하는 것이다. 이 이벤트들을 시간 순으로 처리하면 특정 시점에 동시에 입장해 있는 구간들의 개수를 알 수 있다. 이 개수의 최댓값이 필요한 최소 그룹 수가 된다.

중요한 점은 같은 지점에서 입장과 퇴장이 동시에 발생할 때, 입장 이벤트를 먼저 처리해야 한다는 것이다. 문제의 구간은 닫힌 구간이기 때문에 퇴장 이벤트가 발생해도 그 지점은 여전히 구간에 포함되어 있는 상태이다. 따라서 [1,3]과 [3,5]는 3에서 겹치는 것으로 간주된다. 이를 위해 이벤트를 정렬할 때, 같은 지점에서는 입장 이벤트(+1)가 퇴장 이벤트(-1)보다 먼저 오도록 정렬해야 한다.

코드

function minGroups(intervals: number[][]): number {
  const events: number[][] = [];
  for (const [left, right] of intervals) {
    events.push([left, +1]);
    events.push([right, -1]);
  }

  // 같은 지점이면 입장(+1)이 먼저 — 닫힌 구간이므로 [1,3]과 [3,5]는 겹침
  events.sort((a, b) => a[0] - b[0] || b[1] - a[1]);

  let max = 1;
  let count = 0;
  for (const [_, event] of events) {
    count += event;
    max = Math.max(max, count);
  }

  return max;
}

시간 / 공간 복잡도

시간 복잡도: O(n log n) — 이벤트 정렬
공간 복잡도: O(n) — 이벤트 배열

풀이 2

아이디어

풀이 1과 동일한 아이디어를 투 포인터로도 풀 수 있다.

이벤트를 2D 배열로 저장하는 대신, 구간의 시작과 끝을 각각 다른 배열로 저장해서 정렬한 뒤에, 두 배열을 투 포인터로 탐색하면서 겹치는 구간의 개수를 세는 방식이다.

function minGroups(intervals: number[][]): number {
  const starts = intervals.map(([l]) => l).sort((a, b) => a - b);
  const ends = intervals.map(([, r]) => r).sort((a, b) => a - b);

  let max = 0;
  let count = 0;
  let j = 0;

  for (let i = 0; i < starts.length; i++) {
    if (starts[i] <= ends[j])
      // 닫힘 구간이니까 <= 조건을 써야 함.
      count++; // 입장: 새 구간 시작
    else j++; // 퇴장: 앞선 구간 종료
    max = Math.max(max, count);
  }
  return max;
}

더 직관적인 방법이라며 소개받은 방법이지만, 나는 좀 떠올리기 힘든 방법이라고 생각한다...