[Python] 기간이 겹치지 않도록 하면서 최대 보수를 얻는 아르바이트 조합 찾기

 

DP + 이진탐색

 

1. 각 아르바이트 끝나는 날짜 기준으로 정렬
2. 현재 아르바이트를 포함할지 말지 결정하며 최대 보수 누적
3. 과거에 끝난 아르바이트 중, 현재 아르바이트의 시작일과 겹치지 않는 가장 마지막 아르바이트를 이진 탐색으로 찾기

 

from bisect import bisect_right

def max_earnings(jobs):
    # 아르바이트를 끝나는 날짜 기준으로 정렬
    jobs.sort(key=lambda x: x[1])  # x[1]은 끝나는 날짜 E
    
    # dp[i]는 i번째 아르바이트까지 고려했을 때 얻을 수 있는 최대 보수
    n = len(jobs)
    dp = [0] * n

    # 첫 번째 아르바이트의 보수로 초기화
    dp[0] = jobs[0][2]

    def find_last_non_conflicting(idx):
        """현재 아르바이트와 겹치지 않는 가장 가까운 이전 아르바이트의 인덱스 찾기"""
        # 이진 탐색으로 현재 시작일보다 작거나 같은 끝일을 가진 아르바이트 찾기
        start = jobs[idx][0]
        return bisect_right([job[1] for job in jobs], start) - 1

    # DP로 최대 보수 계산
    for i in range(1, n):
        # 현재 아르바이트를 선택할 경우의 보수
        include = jobs[i][2]
        # 겹치지 않는 마지막 아르바이트 찾기
        last = find_last_non_conflicting(i)
        if last != -1:
            include += dp[last]
        
        # 현재 아르바이트를 선택하지 않는 경우와 비교
        dp[i] = max(include, dp[i - 1])

    # 전체 아르바이트에서의 최대 보수 반환
    return dp[-1]

# 예제 사용
jobs = [
    [1, 3, 50],
    [2, 5, 20],
    [4, 6, 70],
    [6, 7, 30]
]
print(max_earnings(jobs))  # 120