Algorithm Guidecomplexity: O(n log n)

활동 선택 (Activity Selection)

끝나는 시각이 빠른 활동부터 고르면 겹치지 않는 활동을 가장 많이 선택할 수 있다는 그리디 문제입니다. 종료 시각 기준으로 정렬한 뒤 직전 활동과 겹치지 않는 것만 차례로 채택합니다.

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

Activity Selection

A (1~3)

B (2~5)

C (4~6)

D (6~8)

E (5~9)

012345678910

끝나는 시각이 빠른 순으로 정렬한 활동들입니다. 시간이 겹치지 않게 최대한 많이 고르는 것이 목표입니다.

Logic Node1 / 7

Live Python

1def activity_selection(activities):

2 activities.sort(key=lambda a: a[1]) # 끝나는 시각 기준

3 selected = [activities[0]]

4 last_finish = activities[0][1]

5 for start, finish in activities[1:]:

6 if start >= last_finish: # 안 겹치면

7 selected.append((start, finish))

8 last_finish = finish

9 return selected

02 쉽게 이해하기

For Everyone

🔑비유

회의실을 하루에 최대한 많이 빌려주려면, 빨리 끝나는 예약부터 확정하는 것과 같습니다.

💡쉽게 말하면

끝나는 시각이 빠른 활동부터 고르고, 직전에 고른 것과 겹치지 않는 것만 차례로 선택합니다.

이 단순한 규칙만으로 최대 개수가 보장돼요.

📍어디에 쓰나

–회의실·강의실 배정
–작업 스케줄링

03 파이썬 구현 코드

활동 선택 (Activity Selection)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def activity_selection(activities):
    # activities: [(start, finish), ...]
    activities.sort(key=lambda a: a[1])
    selected = [activities[0]]
    last_finish = activities[0][1]
    for start, finish in activities[1:]:
        if start >= last_finish:
            selected.append((start, finish))
            last_finish = finish
    return selected

Guide Progress0%