구간마다 가중치가 있을 때, 서로 겹치지 않는 구간을 최대 4개까지 골라 가중치 합을 최대로 만드는 문제. 합이 같으면 인덱스 배열이 사전순으로 가장 작은 것을 반환해야 한다.

Solution

가중치 있는 구간 스케줄링에 조건이 두 개 붙은 문제.

일단 끝점 기준으로 정렬하면 어떤 구간과 안 겹치는 구간들은 항상 앞쪽에 몰려 있다. 그래서 이분 탐색으로 경계만 찾으면 DP로 풀 수 있다. 경계가 닿아도 겹치는 걸로 치니까 r < l인 것만 세야 한다.

조건 두 개는 상태를 하나씩 늘려주면 된다.
최대 4개니까 고른 개수를 한 차원 추가하고, 사전순은 점수만 들고 있으면 동점일 때 비교할 수가 없으니 (점수, 인덱스 리스트)를 같이 저장한다. 리스트가 최대 4개라 부담도 없다.

dp[c][k] = 앞 k개까지 보고 c개 이하 썼을 때의 (점수, 인덱스 리스트)
dp[c][k+1] = better(dp[c][k], dp[c-1][prev[k]] + 현재 구간)

인덱스 리스트는 붙일 때마다 정렬해줘야 한다. 끝점 기준으로 정렬했으니 원래 인덱스 순서랑 다를 수 있다 (마지막에 한 번만 정렬하면 중간 비교가 이미 틀린다).

시간복잡도는 O(n log n)

Source Code

class Solution:
    def maximumWeight(self, intervals: List[List[int]]) -> List[int]:
        n = len(intervals)
        new_intervals = sorted((r, l, w, i) for i, (l, r, w) in enumerate(intervals))

        prev = []
        for i in range(n):
            prev.append(bisect_left(new_intervals, new_intervals[i][1], key=lambda x: x[0]))

        dp = [[(0, [])] * (n + 1) for _ in range(5)]

        for i in range(n):
            for c in range(1, 5):
                a = dp[c][i]
                b = dp[c-1][prev[i]]
                score = b[0]+new_intervals[i][2]
                itv = sorted(b[1] + [new_intervals[i][3]])

                if a[0] > score or (a[0] == score and a[1] < itv):
                    dp[c][i+1] = a
                else:
                    dp[c][i+1] = (b[0]+new_intervals[i][2], itv)

        return dp[4][n][1]

3414. Maximum Score of Non-overlapping Intervals

Problem Link

Problem Summary

Solution

Source Code