Algorithm Guidecomplexity: O(n log n)

활동 선택 (Activity Selection)

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

01 Explore How It Works

Interactive Step-by-Step

HOVER OR SCROLL

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 Understand It Simply

For Everyone

🔑Analogy

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

💡In Plain Words

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

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

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 활동 선택 (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

04 Frequently Asked Questions

FAQ

What is 활동 선택 (Activity Selection)?+

What is the time complexity of 활동 선택 (Activity Selection)?+

The time complexity of 활동 선택 (Activity Selection) is O(n log n). Follow the step-by-step visualization to see exactly why.

Where is 활동 선택 (Activity Selection) used?+

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

What's a simple analogy for 활동 선택 (Activity Selection)?+

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

→ Greedy — see allRelated

🎯동전 거스름돈 (Coin Change)

O(n)

🎯허프만 코딩 (Huffman Coding)

O(n log n)

Guide Progress0%