Leetcode 를 풀어 보았다.

Pick One 을 눌러 랜덤 문제를 한 개 추출하였다.

1751. Maximum Number of Events That Can Be Attended II

예제를 먼저 살펴보았다.

k 개의 이벤트를 고를 수 있고, 이벤트는 겹치면 안 되는 모양이다. 이벤트의 cost 가 가장 큰 조합을 찾는 문제인 듯 하다.

DP 문제처럼 생겼다.

시작 날짜로 정렬해준 후 f(i, j) 를 i 번째 이후로 최대 j 개의 이벤트를 골랐을 때 최대값이라 하자.

f(i, j) = max (i 번째 이벤트를 고른 경우), (고르지 않은 경우)

라고 할 수 있다.

func maxValue(_ events: [[Int]], _ k: Int) -> Int {
    let events = events.sorted { $0[0] < $1[0] }
    let arr = Array(repeating: -1, count: k + 1)
    var dp = Array(repeating: arr, count: events.count)

    func f(_ i: Int, _ j: Int) -> Int {
        if i >= events.count || j < 1 {
            return 0
        }

        if dp[i][j] != -1 {
            return dp[i][j]
        }

        let e = events[i]

        // let k = events.firstIndex { $0[0] > e[1] } ?? Int.max
        var k = i + 1
        while k < events.count, events[i][1] >= events[k][0] {
            k += 1
        }

        dp[i][j] = max( f(i+1, j), f(k, j-1) + e[2] )

        return dp[i][j]
    }

    return f(0, k)
}

메모이제이션이 없거나 firstIndex 를 사용하면 시간 제한에 걸린다...