JavaScript로 해결하는 활동 선택 문제 (Activity Selection Algorithm)

활동 선택 문제란?

"활동 선택 문제"는 주어진 여러 활동 중에서 겹치지 않도록 가장 많은 활동을 선택하는 문제입니다. 각 활동은 "시작 시간"과 "종료 시간"으로 정의되며, 하나의 활동이 끝난 후에만 다음 활동을 시작할 수 있다는 조건이 있습니다.

이 문제는 "탐욕 알고리즘(Greedy Algorithm)"을 활용하여 빠르고 효율적으로 해결할 수 있는 대표적인 스케줄링 문제입니다.

---

문제 정의

• 활동은 [start, end] 형태의 쌍으로 주어짐
• 하나의 시간대에는 하나의 활동만 가능
• 선택된 활동은 서로 겹치지 않아야 함
• 목표: 선택할 수 있는 활동의 최대 개수를 구함

실생활 예시

• 회의실 예약 시간표 구성
• 작업 스케줄 최적화
• 인터뷰 일정 조정

---

탐욕 알고리즘의 접근 방식

핵심 전략

"종료 시간이 빠른 순"으로 활동을 정렬한 후, 현재 선택된 마지막 활동의 종료 시간보다 늦게 시작하는 활동만을 차례대로 선택합니다.

왜 종료 시간을 기준으로 정렬할까?

종료 시간이 빠르면 다음 활동을 더 일찍 시작할 수 있어 전체적으로 더 많은 활동을 선택할 수 있기 때문입니다.

---

JavaScript 예제 코드

function activitySelection(activities) {
  // 종료 시간을 기준으로 오름차순 정렬
  activities.sort((a, b) => a[1] - b[1]);

  const selected = [];
  let lastEnd = 0;

  for (let [start, end] of activities) {
    if (start >= lastEnd) {
      selected.push([start, end]); // 현재 활동 선택
      lastEnd = end; // 종료 시간 갱신
    }
  }

  return selected;
}

// 예시 실행
const activities = [
  [1, 4],
  [3, 5],
  [0, 6],
  [5, 7],
  [3, 9],
  [5, 9],
  [6, 10],
  [8, 11],
  [8, 12],
  [2, 14],
  [12, 16]
];

const result = activitySelection(activities);
console.log("선택된 활동:", result);

코드 흐름 설명

1. 활동 리스트를 "종료 시간" 기준으로 정렬합니다.
2. lastEnd를 초기화하고, 활동을 하나씩 확인하면서 이전 활동의 종료 시간 이후에 시작하는 경우만 선택합니다.
3. 선택된 활동들을 배열에 저장하여 반환합니다.

출력 결과

선택된 활동: [ [ 1, 4 ], [ 5, 7 ], [ 8, 11 ], [ 12, 16 ] ]

총 4개의 활동이 선택됩니다.

---

시간 복잡도 분석

• 정렬: O(n log n)
• 선택 과정: O(n)
• 총 시간 복잡도: O(n log n)

---

활용 사례

• 컨퍼런스 룸 최적 배정
• 강의실 스케줄 자동 배정 시스템
• 면접 일정 자동 조정

---

주의할 점

• 이 알고리즘은 항상 최적의 해를 보장합니다.
• 단, 활동이 동시에 종료되거나 시작 시간이 동일한 경우 처리 방식에 유의해야 합니다.

---

마무리 및 학습 자료

"활동 선택 문제"는 그리디 알고리즘이 효과적으로 적용되는 전형적인 예제입니다. 핵심은 각 단계에서 가장 최적인 선택이 전체적으로도 최적인 결과로 이어진다는 점을 이해하는 것입니다.

추천 학습 자료:

• GeeksforGeeks: Activity Selection Problem
• LeetCode: Interval Scheduling