Leetcode 3414. Maximum Score of Non-overlapping Intervals

Alpha, Orderly·2026년 9월 12일

leetcode

목록 보기

219/222

문제

2차원 정수 배열 intervals가 주어집니다.
intervals[i] = [li, ri, weighti]이며,

구간 i는 위치 li에서 시작해서 ri에서 끝납니다.
구간 i의 가중치는 weighti입니다.

서로 겹치지 않는 구간을 최대 4개까지 선택할 수 있습니다.

선택한 구간들의 점수(score) 는 선택한 모든 구간의 가중치 합으로 정의됩니다.

가능한 선택 중 점수가 최대가 되도록 구간을 선택하고, 그 구간들의 원래 intervals 배열에서의 인덱스들을 담은 배열을 반환하세요.

최대 점수를 만드는 방법이 여러 개라면, 그중 사전순(lexicographical order)으로 가장 작은 인덱스 배열을 반환해야 합니다.

두 구간이 어떤 점도 공유하지 않을 때 서로 겹치지 않는다고 합니다. 특히 한 구간의 끝점과 다른 구간의 시작점이 같더라도 두 구간은 겹치는 것으로 간주됩니다.

즉,

[1, 3]과 [4, 5] → 겹치지 않음
[1, 3]과 [3, 5] → 겹침

핵심은 최대 4개이므로 반드시 4개를 고를 필요는 없고, ri < lj인 경우에만 두 구간을 함께 선택할 수 있다는 것입니다.

예시

입력: intervals = [[1,3,2],[4,5,2],[1,5,5],[6,9,3],[6,7,1],[8,9,1]]

출력: [2,3]

설명:

인덱스가 2, 3인 구간을 선택할 수 있습니다.

각 구간의 가중치는 각각 5, 3이며, 총 점수는 8입니다.

제한

$1 <= intevals.length <= 5 * 10^4$
$intervals[i].length == 3$
$intervals[i] = [li, ri, weighti]$
$1 <= li <= ri <= 10^9$
$1 <= weighti <= 10^9$

풀이

class Solution:
    def maximumWeight(self, intervals: List[List[int]]) -> List[int]:
        N = len(intervals)

        intervals = [(*interval, i) for i, interval in enumerate(intervals)]
        intervals.sort()

        @cache
        def dp(index: int, left: int) -> Tuple[int, Tuple[int]]:
            if index >= N or left == 0:
                return 0, []

            current = intervals[index]
            next_pos = bisect_left(intervals, current[1] + 1, key=lambda k: k[0])

            skip_weight, skip_list = dp(index + 1, left)

            take_weight, take_list = dp(next_pos, left - 1)

            take_weight += current[2]
            take_list = sorted([*take_list, current[3]])
            take_list = tuple(take_list)

            skip = (skip_weight, tuple(skip_list))
            take = (take_weight, tuple(take_list))

            if skip_weight != take_weight:
                return max(skip, take)

            if skip_list < take_list:
                return skip
            else:
                return take

        return dp(0, 4)[1]