Job Sequencing Problem

Q: 작업 스케줄링 문제의 시간 복잡도는 얼마인가요?

O(n log n) 이고, 공간 복잡도는 O(n) 입니다. 각 마감 시간부터 거꾸로 빈 슬롯을 탐색하면 마감 시간이 대부분 클 때 O(n²) 의 비용이 듭니다.

보통그리디 정렬

+10

n개의 작업이 두 배열로 주어집니다. 작업 i는 마감 시간 deadline[i]까지 완료하면 profit[i]의 이익을 얻습니다. 각 작업은 한 단위의 시간이 걸리고, 시간 0부터 한 번에 하나의 작업을 수행하며, 원하는 작업은 건너뛸 수 있습니다. 마감 시간이 2인 작업은 0부터 1까지 또는 1부터 2까지 수행할 수 있습니다.

얻을 수 있는 총이익의 최댓값을 반환하세요.

함수

jobSequencing(deadline: integer-array, profit: integer-array) → integer

deadlineinteger-array: 각 작업을 완료해야 하는 시점으로, 1부터 n까지
profitinteger-array: 각 작업의 수익; profit[i]는 deadline[i]에 해당합니다
반환값integer: 모든 작업이 마감일까지 완료될 수 있을 때의 최대 총이익

제약 조건

1 ≤ deadline.length == profit.length ≤ 5000
1 ≤ deadline[i] ≤ n, 여기서 n은 작업의 개수입니다.
1 ≤ profit[i] ≤ 10⁵
배열은 정렬되어 있지 않습니다. 여러 작업이 동일한 마감일이나 이익을 공유할 수 있습니다.

예제

입력: deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
출력: 120
설명: 마감 시간이 1인 두 작업 중 하나만 수행할 수 있으므로 가치가 50인 작업을 수행하세요. 그러면 가치가 30인 작업은 마감 시간 2에, 가치가 40인 작업은 마감 시간 3에 완료됩니다. 50 + 30 + 40 = 120.

입력: deadline = [1, 1, 1]profit = [5, 9, 7]
출력: 9
설명: 세 작업 모두 시간 1까지 끝나야 하며, 그전에 들어갈 수 있는 작업은 하나뿐입니다. 그중 가장 좋은 작업의 수익은 9입니다.

후속 질문

작업 i가 1단위 시간이 아니라 duration[i]단위의 시간을 소요한다면 어떨까요? 가장 수익성이 높은 작업을 먼저 선택하는 것이 여전히 최상의 총합을 얻는 방법일까요?

풀이

어떤 작업을 남길지와 언제 실행할지를 정합니다. 하나의 탐욕 규칙으로 둘 다 결정할 수 있습니다. 수익성이 가장 높은 작업부터 차례로 선택해 마감 시각까지 비어 있는 가장 늦은 슬롯에 넣고, 빈 슬롯이 없으면 건너뜁니다. 서로소 집합을 사용하면 이미 예약된 슬롯을 하나씩 지나가지 않고도 해당 슬롯을 찾을 수 있습니다.

이익을 기준으로 탐욕적으로 선택하며 빈 슬롯을 탐색

핵심 아이디어

시간을 슬롯으로 나눕니다. 슬롯 t는 t-1부터 t까지이고, 마감 시간이 d인 작업은 슬롯 1부터 d까지 사용할 수 있으며, 어떤 마감 시간도 n을 초과하지 않습니다. 가장 수익성이 높은 작업을 먼저 선택해도 안전합니다. 사용할 수 있는 슬롯이 모두 예약되어 있다면, 그중 하나의 슬롯에 있는 작업과 교체해도 수익이 같거나 더 크기 때문입니다. 가장 늦은 슬롯에 예약하는 것도 안전합니다. 마감 시간이 이른 작업은 앞쪽 슬롯만 사용할 수 있기 때문입니다.

비용은 슬롯을 훑는 데 듭니다. 모든 마감 시간이 n이면, k번째 작업은 이미 예약된 슬롯 k-1개를 지나갑니다. 대략 n²/2번, 즉 n = 5000일 때 1,250만 단계입니다.

알고리즘

작업을 이익이 큰 순서대로 정렬하고, 각 작업의 마감 기한과 이익을 함께 유지합니다.
모두 false인 n + 1개의 플래그로 배열 taken을 만듭니다.
각 작업에 대해 마감 기한부터 1까지 t를 줄여 가며, 사용되지 않은 첫 번째 슬롯에서 멈춥니다.
그런 슬롯을 찾았다면 사용된 것으로 표시하고 작업의 이익을 total에 더합니다.
total을 반환합니다.

def jobSequencing(deadline, profit):
    n = len(deadline)
    taken = [False] * (n + 1)  # taken[t]: the time unit from t-1 to t is booked
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        for t in range(deadline[i], 0, -1):  # latest free slot first
            if not taken[t]:
                taken[t] = True
                total += profit[i]
                break
    return total

서로소 집합으로 빈 슬롯을 관리하며 이익이 큰 순서대로 선택

핵심 아이디어

스캔은 이미 예약된 슬롯을 계속해서 다시 살펴봅니다. 슬롯 0부터 n까지를 대상으로 하는 서로소 집합은 이를 건너뜁니다. 슬롯 t가 비어 있는 동안에는 parent[t] = t이고, 슬롯을 예약하면 parent[t] = t-1로 설정되므로, 마감 시간에서 포인터를 따라가면 가장 늦은 빈 슬롯에 도달합니다. 슬롯 0에 도달하면 남은 슬롯이 없다는 뜻입니다. 경로 절반 줄이기는 지나가는 각 슬롯이 두 단계 앞을 가리키게 하므로, 이후의 탐색은 더 짧아집니다.

세 번째 예시에서는 가치가 60과 50인 작업이 각각 슬롯 2와 1을 예약합니다. 가치가 20이고 마감 시간이 2인 작업은 2에서 1을 거쳐 0으로 이동한 뒤 건너뜁니다.

정렬에는 O(n log n)이 걸리고, 경로 절반 줄이기를 사용하면 각 조회에는 분할 상환 기준 O(log n)이 걸리므로 전체 시간 복잡도는 계속 O(n log n)입니다.

알고리즘

작업을 이익이 큰 순서대로 정렬하고, 각 작업의 마감일과 이익을 함께 유지합니다.
0부터 n까지 모든 슬롯 t에 대해 parent[t] = t로 설정합니다.
각 작업에 대해 slot = deadline에서 시작하여 parent[slot] == slot이 될 때까지 parent를 따라가면서 경로를 절반씩 줄입니다.
slot > 0이면 작업의 이익을 더하고 parent[slot] = slot-1로 설정합니다. 그렇지 않으면 작업을 건너뜁니다.
합계를 반환합니다.

def jobSequencing(deadline, profit):
    n = len(deadline)
    # following parent from slot t ends at the latest free slot at or before t; 0 means none is left
    parent = list(range(n + 1))
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        slot = deadline[i]
        while parent[slot] != slot:
            parent[slot] = parent[parent[slot]]  # halve the path as you go
            slot = parent[slot]
        if slot > 0:
            total += profit[i]
            parent[slot] = slot - 1  # booked: its chain continues at the slot before it
    return total

함정과 경계 사례

작업을 가장 먼저 비어 있는 슬롯에 배치하기. 세 번째 예시에서는 수익이 60인 작업이 슬롯 1을 차지하고, 수익이 50인 작업은 배치되지 못해 110 대신 80을 얻습니다.
마감일 순서대로 작업을 선택하기. 마감일이 [1, 1]이고 수익이 [1, 100]이면, 수익이 낮은 작업이 유일한 슬롯을 차지해 100 대신 1을 얻습니다.
슬롯 배열의 크기를 n + 1이 아니라 n으로 지정하기. 그러면 마감일이 n인 경우 배열의 끝을 넘어 읽게 됩니다.
수익만 따로 정렬하기. 각 마감일은 해당 수익과 함께 이동해야 합니다.
재귀로 찾기 단계를 작성하기. 예약된 슬롯이 수천 개 이어진 경우 스택이 넘칠 수 있으므로 반복문을 사용하세요.

자주 묻는 질문3

작업 스케줄링 문제의 시간 복잡도는 얼마인가요?

O(n log n)이고, 공간 복잡도는 O(n)입니다. 각 마감 시간부터 거꾸로 빈 슬롯을 탐색하면 마감 시간이 대부분 클 때 O(n²)의 비용이 듭니다.

작업 스케줄링에서 탐욕적 접근법은 왜 작동할까요?

최적의 일정에는 가장 수익성이 높은 작업이 포함됩니다. 이 작업이 빠져 있고 마감일 이전의 슬롯이 비어 있다면, 이 작업을 추가하면 더 많은 수익을 얻습니다. 해당 슬롯이 모두 예약되어 있다면, 다른 작업과 바꿔 넣어도 수익이 최소한 같아집니다. 나머지 작업에도 같은 논리를 적용할 수 있습니다.

작업 스케줄링을 힙으로도 해결할 수 있을까요?

네. 작업을 마감일순으로 정렬하고 각 수익을 최소 힙에 넣으세요. 힙에 들어 있는 작업 수가 현재 마감일까지 수행할 수 있는 작업 수보다 많아지면 가장 작은 수익을 꺼내세요. 마지막에 힙에는 최적의 작업 집합이 남고, 그 합이 답이며, 시간 복잡도는 O(n log n)입니다.

def jobSequencing(deadline, profit):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

deadline = [3, 1, 2, 3, 1]
profit = [40, 35, 30, 25, 50]

예상 출력