♟ 가장 많은 일정을 소화하는 법, 활동 선택(Activity Selection)

관련글 : 

그리디	https://waydd.tistory.com/91
허프만 인코딩	https://waydd.tistory.com/110

 

 

1. 활동 선택 문제

 

하나의 자원을 여러 활동들이 공유할 때, 겹치지 않게 할 수 있는 최대 개수의 활동을 선택 하는 그리디 + 정렬 기반 문제

• 각 활동은 시작 시간(start) 과 종료 시간(end) 이 주어짐
  (단, 모든 활동은 단일 자원 사용, 한 시점에 하나의 활동만 가능)
• 종료 시간이 가장 빠른 활동부터 선택 (선택시 비겹치게) 하는 것이 전역 최적을 보장 (그리디)
  → 모든 활동을 종료 시간 기준으로 오름차순 정렬 후, 선형 탐색(먼저 끝나는 것부터) + 겹치지 않으면 선택
  → 현재 활동의 시작 시간 ≥ 이전 활동의 종료 시간 이면 선택 ( 두 활동이 겹치지 않아야 선택 가능 )
  → 시간 복잡도 (전체) : O(N log N) (정렬) + O(N) (선택 반복) = O(N log N)
• 자원(시간) 최적 사용 을 목적으로 하는 강의실 스케줄링/최소 개수, 회의실 배정, CPU 작업 배정 등 에 사용
• 기본은 종료 시간 기준 정렬 + 그리디
  → 다양한 변형(이익, 회의실 수, 선점 등) 에서는 그리디 + 정렬 + 힙 조합으로 확장

※ 그리디 알고리즘(종료 시간 기준 정렬) 이 항상 최적해를 보장하는 이유
(문제 조건) 하나의 자원을 여러 활동이 공유 + 두 활동은 시간이 겹치면 X +  최대한 많은 활동을 선택
(가정) 최적 해 O가 있고, 그리디 해 G는 O와 다른 선택을 했다. 그리디는 종료 시간이 가장 빠른 활동 a를 선택했지만, 최적 해는 다른 활동 b를 선택
(비교 조건 1) a.end ≤ b.end (왜냐하면 a는 가장 빨리 끝나는 활동이므로)
(비교 조건 2) a와 b는 둘 다 첫 번째 선택 가능한 활동이라고 가정
- O에서 b를 제거하고 a로 교체해도, 이후 가능한 활동의 집합은 같거나 더 많음 ( 교환 증명 )
  → 즉, a를 선택한 것이 나쁠 이유가 없다
  → 따라서 그리디의 선택이 항상 최적 해
- 가장 먼저 끝나는 활동을 선택하면 이후에 선택할 수 있는 활동의 수가 최대화

※ 반대로 시작 시간 기준 정렬하면 틀릴 수 있는가
(문제 정렬) [(1, 10), (2, 3), (3, 4)]
- 첫 번째 활동(1,10)을 고르면, 나머지를 못 고름, 총 1개
- 종료 시간 기준 정렬하면: [(2, 3), (3, 4), (1, 10)]
  → (2,3), (3,4) 선택 가능, 총 2개 (정답)
- 시작 시간이 빠르다고 해서 전체 최적 선택이 되지 않기 때문
- 그리디 로서 가장 유리한 선택 하려면 종료 시간 기준으로 판단해야 함

 

 

2. 대표 예제 설명

 

- 활동 선택 과정 시각화

• 6개의 활동, 각 활동: (시작, 종료), 선택 가능한 활동의 최대 개수는 3개 
• 종료 시간이 빠른 순서로 : A1 → A2 → A3 → A4 → A5 → A6
• 초기 last_end_time = 0, count = 0
• 최종 선택된 활동 : A1 (1 ~ 4), A4 (5 ~ 7), A5 (8 ~ 9)

	시작	종료	정렬 후 순서	조건 확인 ( start ≥ last_end_time )	선택 여부	last_end_time 갱신	count
A1	1	4	1번째	1 ≥ 0	선택	4	1
A2	3	5	2번째	3 ≥ 4 (겹침)	건너뜀	유지(4)	1
A3	0	6	3번째	0 ≥ 4 (겹침)	건너뜀	유지(4)	1
A4	5	7	4번째	5 ≥ 4	선택	7	2
A5	8	9	5번째	8 ≥ 7	선택	9	3
A6	5	9	6번째	5 ≥ 9 (겹침)	건너뜀	유지(9)	3

 

 

- 주요 변수 설명

	역할	자료형	설명 예시
activities	활동 목록	List[Tuple[int, int]]	각 활동의 (시작 시간, 종료 시간) 쌍을 저장 ex) [(1, 4), (3, 5), (0, 6)]
n	활동 개수	int	전체 활동의 수. len(activities)로 할당
activities.sort(key=lambda x: x[1])	종료 시간 기준 정렬	-	가장 빨리 끝나는 활동을 먼저 선택하기 위한 정렬 기준
last_end_time	이전에 선택된 활동의 종료 시각	int	다음 활동과 겹치는지 판단하기 위해 사용. 초기값은 0 또는 -1
count	선택된 활동 개수	int	조건을 만족하면 증가시키는 최종 출력값

 

 

- 코드 구현

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
activities.sort(key=lambda x: x[1])  # 종료 시간 기준 정렬

last_end_time = 0
count = 0

for start, end in activities:
    if start >= last_end_time:  # 겹치지 않으면 선택
        count += 1
        last_end_time = end  # 종료 시간을 갱신

print(count)  # 출력: 3

 

 

3. 유사 문제 및 확장 문제

 

- 기본 활동 선택 문제 (Activity Selection)

• 겹치지 않게 최대한 많은 활동 선택 ( 종료 시간 기준 정렬 + 그리디 선택 )
• 시간 복잡도 : O(N log N) (정렬 + 선택 순회)
• 회의실 배정 등 간단한 스케줄링 문제 에 해당

def activity_selection(activities):
    # 종료 시간 기준 정렬
    activities.sort(key=lambda x: x[1])

    last_end_time = 0
    count = 0

    for start, end in activities:
        if start >= last_end_time:
            count += 1
            last_end_time = end

    return count

# 예제 입력
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
print(activity_selection(activities))  # 출력: 3

 

- 최소 회의실 개수 문제 (우선순위 큐 사용)

• 모든 회의를 수용하려면 회의실 최소 몇 개가 필요한가 ( 시작/종료 따로 정렬 + Min-Heap으로 겹치는 회의 추적 )
• 시간 복잡도 : O(N log N) ( 정렬 + 힙 사용 O(N log N) )

import heapq

def min_meeting_rooms(intervals):
    if not intervals:
        return 0

    # 시작 시간 기준 정렬
    intervals.sort(key=lambda x: x[0])

    heap = []  # 종료 시간 기준 최소 힙

    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)  # 기존 회의실 사용 가능

        heapq.heappush(heap, end)  # 새 회의실 필요

    return len(heap)

# 예제 입력
meetings = [(0, 30), (5, 10), (15, 20)]
print(min_meeting_rooms(meetings))  # 출력: 2

 

- 이익이 있는 작업 선택 ( 이익이 음수일 수 있음 )

• 겹치지 않는 작업 중 총 이익 최대화 ( 종료 시간 기준 정렬 + DP + 이분 탐색 )
• 시간 복잡도 : O(N log N) ( 정렬 + 각 DP마다 이진 탐색 O(log N) )

import bisect

def max_profit(jobs):
    # jobs: (start, end, profit)
    jobs.sort(key=lambda x: x[1])  # 종료 시간 기준 정렬

    # 종료 시간만 따로 저장 (이진 탐색용)
    ends = [job[1] for job in jobs]
    dp = [0] * (len(jobs) + 1)

    for i in range(1, len(jobs) + 1):
        start, end, profit = jobs[i - 1]
        # 이 작업 이전에 끝나는 가장 마지막 작업 찾기
        idx = bisect.bisect_right(ends, start)  # 시작 이전 종료를 가진 마지막 인덱스
        dp[i] = max(dp[i - 1], dp[idx] + profit)

    return dp[-1]

# 예제 입력
jobs = [(1, 3, 50), (3, 5, 20), (6, 19, 100), (2, 100, 200)]
print(max_profit(jobs))  # 출력: 250

 

- 선점 가능한 작업 스케줄링

• 긴 작업이 진행 중이더라도, 더 중요하거나 급한 작업이 오면 중단하고 선점 ( 이벤트 + heap )
• 작업 도착/종료를 이벤트로 정리 (Event Queue)
  + 우선순위 기준으로 현재 실행 중 작업을 중단하고 교체
  + heapq로 현재 실행 중인 작업을 관리
• 음수 이익이 들어오면 dp[i] = max(dp[i-1], dp[idx] + profit) 에서 
  → 이번 작업을 포함하지 않을 때의 최대 이익 (dp[i-1]) vs 이번 작업을 포함할 때의 이익 (dp[idx] + profit)
  → profit < 0이면, dp[idx] + profit이 더 작을 수 있으므로 자연스럽게 포함하지 않게 됨 (자동 판단)
• 시간 복잡도 : 이벤트 개수 × log(N) = O(N log N)

import heapq

def preemptive_scheduling(tasks):
    # tasks: (도착 시간, 실행 시간, 우선순위)
    events = sorted(tasks, key=lambda x: x[0])
    time = 0
    idx = 0
    running = []
    
    while idx < len(events) or running:
        # 새로 도착한 작업 추가
        while idx < len(events) and events[idx][0] <= time:
            arrival, duration, priority = events[idx]
            heapq.heappush(running, (priority, duration, arrival))
            idx += 1
        
        if running:
            priority, duration, arrival = heapq.heappop(running)
            time += 1  # 단위 시간 선점 실행
            duration -= 1
            if duration > 0:
                heapq.heappush(running, (priority, duration, arrival))
        else:
            time = events[idx][0]  # 다음 작업 도착까지 대기

    return time

# 예제
tasks = [(0, 3, 2), (1, 2, 1), (3, 1, 3)]
print(preemptive_scheduling(tasks))  # 출력: 5

 

- 실시간 추가 & 온라인 스케줄링

• 실시간으로 회의가 들어오고, 현재 상황에서 바로 판단해서 회의실을 배정하거나 거절 (온라인 알고리즘)
• 요청이 도착할 때마다 현재 가장 빨리 비는 회의실에 배정 + Min-Heap (종료 시간 기준)으로 관리
• 시간 복잡도 : 각 요청당 O(log K) (회의실 개수 K) = O(N log K)

import heapq

def online_schedule(requests):
    heap = []  # 종료 시간 저장
    for start, end in sorted(requests):
        if heap and heap[0] <= start:
            heapq.heappop(heap)  # 기존 회의실 사용
        heapq.heappush(heap, end)
    return len(heap)

# 예제
requests = [(1, 4), (2, 5), (3, 6), (8, 9)]
print(online_schedule(requests))  # 출력: 3

 

 

4. 요약 정리

 

- 패턴 정리

종료 시간 기준 정렬	활동 선택 문제에서 핵심. 더 많은 활동을 넣기 위해 먼저 끝나는 걸 고름
정렬 후 조건 비교	반복문 돌면서 start ≥ last_end_time 조건으로 선택 여부 결정
정렬 + 누적 처리	정렬 후 활동 수, 이익 누적, 회의실 수 등 다양한 문제로 확장 가능

 

 

- 상황과 대응 전략

	대응 전략
회의가 정확히 종료 시각에 시작되는 경우	start >= end 조건이므로 겹치지 않음 → 선택 가능
회의 시간이 0인 경우 (start == end)	정상 처리 가능. 단, 구현 시 >= 비교를 써야 함
이익이 음수일 경우	DP 구조에서 자동으로 걸러짐 (max로 비교함)
회의가 동시간대에 몰려 있는 경우	heap을 쓰는 회의실 문제 확장으로 대비해야 함

 

 

- 그리디 알고리즘 사용하는 경우 정리 (최적해 보장)

	전략	설명
활동 선택 문제 (회의실 배정)	종료 시간 기준 정렬	겹치지 않는 활동 최대 선택
호텔 대실	시작 시간 기준 정렬 + 힙	겹치는 횟수 = 필요한 자원 수
강의실 배정	시작/종료 정렬 + 우선순위 큐	회의실 수 최소화
이익 있는 스케줄링	DP + 이진탐색	이익 최대화 문제로 확장