Activity Selection Problem

Q: 활동 선택 문제의 시간 복잡도는 무엇인가요?

완료 시간을 기준으로 정렬하는 데 O(n log n) 이 걸리고, 그다음의 그리디 패스에는 O(n) 이 걸리므로 정렬이 지배적입니다. 활동이 이미 완료 시간 순으로 정렬되어 있다면 패스만으로 O(n) 시간과 O(1) 의 추가 공간을 사용해 문제를 해결할 수 있습니다.

Q: 한 회의실에서 N개의 회의 문제란 무엇인가?

회의를 이용해 같은 문제를 설명합니다. 방 하나, N 개의 회의가 있고, 회의는 이전 회의가 끝난 후에만 시작할 수 있습니다. 회의를 종료 시간 순으로 정렬한 뒤, 마지막으로 선택한 회의가 끝난 후에 시작하는 회의를 각각 선택합니다. 선택한 회의 목록을 만들려면 선택한 회의의 인덱스를 기록하고, 종료 시간이 같으면 인덱스가 더 작은 회의를 우선합니다.

쉬움그리디 정렬

+10

활동 i는 시간 start[i]부터 시간 finish[i]까지 진행됩니다. 한 사람은 한 번에 하나의 활동만 할 수 있으며, 다음 활동은 이전 활동이 끝난 후에 엄격히 시작해야 합니다. 다른 활동이 끝나는 정확한 시간에 시작하는 활동은 그 활동에 이어서 할 수 없습니다.

한 사람이 할 수 있는 활동의 최대 개수를 반환하세요.

함수

maxActivities(start: integer-array, finish: integer-array) → integer

startinteger-array: 각 활동의 시작 시간
finishinteger-array: 각 활동의 종료 시각; finish[i]는 start[i]에 해당합니다
반환값integer: 한 사람이 차례로 할 수 있는 활동의 최대 개수

제약 조건

1 ≤ start.length == finish.length ≤ 5000
0 ≤ start[i] ≤ finish[i] ≤ 10⁵
활동은 같은 시각에 시작하고 끝날 수 있습니다. 배열은 정렬되어 있지 않습니다.

예제

입력: start = [10, 12, 20, 14, 25, 21]finish = [13, 16, 24, 19, 30, 22]
출력: 4
설명: 10에서 13까지, 14에서 19까지, 21에서 22까지, 25에서 30까지를 선택하면 4가 됩니다. 5는 불가능합니다. 10에서 13까지는 12에서 16까지와 겹치고, 21에서 22까지는 20에서 24까지와 겹치기 때문입니다.

입력: start = [1, 5, 9]finish = [5, 9, 12]
출력: 2
설명: 5에서 9까지의 활동은 첫 번째 활동이 끝나는 정확한 시간에 시작하므로, 첫 번째 활동 뒤에 올 수 없습니다. 1에서 5까지 한 다음 9에서 12까지 하면 되므로 답은 2입니다.

입력: start = [0, 2, 5, 8]finish = [100, 4, 7, 10]
출력: 3
설명: 0부터 100까지의 활동은 다른 모든 활동과 겹칩니다. 이를 제외하면 2부터 4까지, 5부터 7까지, 8부터 10까지가 차례대로 들어맞습니다: 3.

후속 질문

이제 두 사람이 병렬로 작업하며, 각자 한 번에 하나의 활동을 합니다. 두 사람이 함께 몇 가지 활동을 할 수 있으며, 각 활동은 누가 맡아야 할까요?

풀이

모든 활동의 부분집합을 하나씩 시도하면 지수 시간이 걸립니다. 대신 탐욕적 규칙 하나로 문제를 해결할 수 있습니다. 아직 들어맞는 활동 중 항상 가장 먼저 끝나는 활동을 선택하세요. 종료 시간을 기준으로 정렬하면 이 규칙을 한 번만 순회해 적용할 수 있습니다.

가장 먼저 끝나는 것을 계속해서 선택하세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

가장 먼저 끝나는 활동은 다른 어떤 활동보다도 최소한 첫 번째 선택으로서 나쁘지 않습니다. 그 활동을 선택해도 더 늦게 끝나지 않으므로, 다른 활동을 첫 번째로 선택한 뒤에 할 수 있는 활동은 이 활동을 선택한 뒤에도 할 수 있으며, 이를 바꾸어도 활동 개수는 유지됩니다. 그 활동을 선택한 뒤에는 그 활동이 끝난 다음에 시작하는 활동들을 대상으로 문제가 반복됩니다.

첫 번째 예에서는 10부터 13까지를 선택한 다음, 14부터 19까지, 21부터 22까지, 25부터 30까지를 선택합니다. 총 네 개입니다.

선택할 때마다 n개의 활동을 모두 확인하므로, 비용은 n에 답의 개수를 곱한 값입니다. 5000개의 활동이 모두 차례로 들어맞으면, 확인 횟수는 2500만 번입니다.

알고리즘

모든 시작 아래에서 count = 0과 lastFinish = -1로 설정합니다.
모든 활동을 살펴보고 start[i] > lastFinish를 만족하면서 가장 먼저 끝나는 활동을 찾습니다.
그러한 활동이 없으면 count를 반환합니다.
그렇지 않으면 count에 1을 더하고 lastFinish를 해당 활동의 종료 시각으로 설정한 다음 다시 살펴봅니다.

def maxActivities(start, finish):
    n = len(start)
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    while True:
        # among the activities that start after last_finish, find the one that ends first
        pick = -1
        for i in range(n):
            if start[i] > last_finish and (pick == -1 or finish[i] < finish[pick]):
                pick = i
        if pick == -1:
            return count
        count += 1
        last_finish = finish[pick]

완료 시간을 기준으로 정렬하고 탐욕적으로 선택합니다

핵심 아이디어

종료 시간을 기준으로 한 번 정렬하면 위의 탐색에서 활동을 찾았던 순서대로 활동을 만나게 됩니다. 정렬된 목록을 훑으면서 선택한 마지막 활동의 종료 시간인 lastFinish를 기억하세요. start[i] > lastFinish인 활동은 여전히 선택할 수 있는 활동 중 가장 먼저 끝나는 활동이므로 선택하세요. 나머지 활동은 모두 마지막으로 선택한 활동과 겹치므로 건너뛰어도 손해가 없습니다.

정렬하면 첫 번째 예시는 10부터 13까지, 12부터 16까지, 14부터 19까지, 21부터 22까지, 20부터 24까지, 25부터 30까지입니다. 첫 번째, 세 번째, 네 번째, 여섯 번째 활동을 선택합니다. 12는 13보다 늦지 않고, 20은 22보다 늦지 않기 때문입니다.

종료 시간이 같은 경우에는 별도의 규칙이 필요하지 않습니다. t에 끝나는 활동을 선택하면, t에 끝나는 다른 모든 활동은 t 또는 그 이전에 시작하므로 건너뜁니다.

알고리즘

finish를 기준으로 활동을 정렬하고, 각 시작 시간도 해당 종료 시간과 함께 이동합니다.
count = 0과 lastFinish = -1로 설정합니다.
해당 순서대로 각 활동에 대해 start[i] > lastFinish이면 count에 1을 더하고 lastFinish = finish[i]로 설정합니다.
count를 반환합니다.

def maxActivities(start, finish):
    order = sorted(range(len(start)), key=lambda i: finish[i])  # earliest finish first
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    for i in order:
        if start[i] > last_finish:
            count += 1
            last_finish = finish[i]
    return count

함정과 경계 사례

시작 시간을 기준으로 정렬하기. 세 번째 예시에서는 0부터 100까지의 활동이 가장 먼저 시작되어 나머지 세 활동을 모두 막습니다.
가장 짧은 활동을 먼저 선택하기. 1부터 5까지, 5부터 6까지, 6부터 10까지의 활동이 있을 때 가장 짧은 활동은 5부터 6까지이며, 나머지 두 활동 모두와 겹칩니다. 1부터 5까지와 6부터 10까지를 선택하면 2개를 얻습니다.
≥ 대신 >로 비교하기. 두 번째 예시에서 이 경우 2가 아니라 3을 반환합니다.
finish만 따로 정렬하기. 각 시작 시간은 해당 종료 시간과 함께 이동해야 합니다. 그렇지 않으면 시작 시간이 잘못된 활동과 짝을 이루게 됩니다.
lastFinish를 0으로 시작하기. 그러면 0부터 1까지의 활동 하나만 있는 경우 건너뛰게 됩니다. 0 > 0은 거짓이기 때문입니다.

자주 묻는 질문3

활동 선택 문제의 시간 복잡도는 무엇인가요?

완료 시간을 기준으로 정렬하는 데 O(n log n)이 걸리고, 그다음의 그리디 패스에는 O(n)이 걸리므로 정렬이 지배적입니다. 활동이 이미 완료 시간 순으로 정렬되어 있다면 패스만으로 O(n) 시간과 O(1)의 추가 공간을 사용해 문제를 해결할 수 있습니다.

한 회의실에서 N개의 회의 문제란 무엇인가?

회의를 이용해 같은 문제를 설명합니다. 방 하나, N개의 회의가 있고, 회의는 이전 회의가 끝난 후에만 시작할 수 있습니다. 회의를 종료 시간 순으로 정렬한 뒤, 마지막으로 선택한 회의가 끝난 후에 시작하는 회의를 각각 선택합니다. 선택한 회의 목록을 만들려면 선택한 회의의 인덱스를 기록하고, 종료 시간이 같으면 인덱스가 더 작은 회의를 우선합니다.

활동 선택 문제는 동적 프로그래밍인가요?

그럴 수도 있지만, 꼭 그럴 필요는 없습니다. 종료 시간순으로 정렬된 활동들을 대상으로, 각 활동까지 포함했을 때 끝나는 활동 수가 가장 많은 경우를 저장하는 표를 사용하면 O(n²) 시간에 답을 구할 수 있습니다. 탐욕적 선택은 항상 안전하므로 한 번만 순회하면 충분합니다. 활동에 값이 부여되어 있고 그 총합을 최대화하려는 경우에는 표가 적합한 도구가 됩니다.

def maxActivities(start, finish):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

start = [10, 12, 20, 14, 25, 21]
finish = [13, 16, 24, 19, 30, 22]

예상 출력