Leetcode 1751. Maximum Number of Events That Can Be Attended II

https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended-ii/description/

Maximum Number of Events That Can Be Attended II - LeetCode

 

문제

events 배열이 주어진다. 이 배열은 events[i] = [startDay, endDay, value]로 구성되어 있다. i번째 event는 events[i]의 startDay에서 시작해 endDay 이하까지 이어진다. 그리고 이 이벤트를 참가하면 value에 해당하는 점수를 받을 수 있다. 그리고 정수 k 역시 함께 주어지는데 이는 이벤트에 참가할 수 있는 횟수를 의미한다.

 

동시에 하나의 이벤트에 참여할 수 있으며,  이벤트에 참석했다면 이벤트가 끝나는 시간까지 다른 이벤트로 갈 수 없다. 끝나는 시각 endDay에 시작하는 다른 이벤트에는 참여할 수 없기 때문에 만약 endDay가 2인 경우 새로운 이벤트에 참여하기 위해서는 startDay가 최소 3이 되어야 참석할 수 있다.

 

이 때 받을 수 있는 최대의 점수를 구하여라!

 

코드

class Solution:

    def maxValue(self, events: list[list[int]], k: int) -> int:

        if k == 1:

            return max([x[2] for x in events])

        events.sort(key=lambda x: x[0])

        m = {}

        for (s, end, value) in events:

            start = s - 1

            # check key less then current key(end)

            mapped = map(lambda x: (x, sum(

                m[x][:k-1])), filter(lambda x: x <= start, m.keys()))

            maxKey = sorted(mapped, reverse=True, key=lambda x: x[1])

            if maxKey:

                newOne = m[maxKey[0][0]] + [value]

                if end in m:

                    origin = m[end]

                    if sum(origin) < sum(newOne):

                        m[end] = newOne

                    elif sum(origin) == sum(newOne) and len(origin) > len(newOne):

                        m[end] = newOne

                else:

                    m[end] = newOne

            else:

                if end not in m or sum(m[end]) < value:

                    m[end] = [value]

            # cut off when longer than k

            if len(m[end]) >= k:

                m[end] = sorted(m[end], reverse=True)[:k]

        # print(m)

        answer = max([sum(m[x]) for x in m.keys()])

        # print(answer, end="\n\n")

        return answer

---

약 3시간이 걸린 코드... 간단하게 설명하면 차곡차곡 value의 합을 쌓아두면서 앞으로 나아가는 방식이다.