[LeetCode] 2054. Two Best Non-Overlapping Events (Python)

 

난이도: Medium

 

문제 설명

---

You are given a 0-indexed 2D integer array of events where events[i] = [startTime_i, endTime_i, value_i]. The ith event starts at startTime_i and ends at endTime_i, and if you attend this event, you will receive a value of value_i. You can choose at most two non-overlapping events to attend such that the sum of their values is maximized.

Return this maximum sum.

Note that the start time and end time is inclusive: that is, you cannot attend two events where one of them starts and the other ends at the same time. More specifically, if you attend an event with end time t, the next event must start at or after t + 1.

 

문제 예제

---

Example 1:

Input: events = [[1,3,2],[4,5,2],[2,4,3]]
Output: 4
Explanation: Choose the green events, 0 and 1 for a sum of 2 + 2 = 4.

 

Example 2:

Input: events = [[1,3,2],[4,5,2],[1,5,5]]
Output: 5
Explanation: Choose event 2 for a sum of 5.

 

Example 3:

Input: events = [[1,5,3],[1,5,1],[6,6,5]]
Output: 8
Explanation: Choose events 0 and 2 for a sum of 3 + 5 = 8.

 

제한 사항

---

• 2 <= events.length <= 10^5
• events[i].length == 3
• 1 <= startTime_i <= endTime_i <= 10^9
• 1 <= value_i <= 10^6

 

✏️ Solution(솔루션)

---

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        answer = 0
        n = len(events)
        events.sort()

        max_value = [0] * n
        max_value[-1] = events[-1][2]

        for i in range(n-2, -1, -1):
            max_value[i] = max(max_value[i+1], events[i][2])

        for i, event in enumerate(events):
            answer = max(answer, event[2])
            left, right = 0, n-1
            idx = -1
            while left <= right:
                mid = (left + right) // 2

                if events[mid][0] > event[1]:
                    idx = mid
                    right = mid - 1
                else:
                    left = mid + 1

            if idx != -1:
                answer = max(answer, event[2] + max_value[idx])

        return answer

 

 

처음에는 다음과 같이 코드를 제출했는데

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        answer = 0
        n = len(events)
        events.sort()

        value = []
        for s,e,v in events:
            value.append(v)

        for i, event in enumerate(events):
            answer = max(answer, event[2])
            left, right = 0, n-1
            idx = -1
            while left <= right:
                mid = (left + right) // 2

                if events[mid][0] > event[1]:
                    idx = mid
                    right = mid - 1
                else:
                    left = mid + 1

            if idx != -1:
                answer = max(answer, event[2] + max(value[idx:]))

        return answer

 

Time Limit Exceeded에 걸리는 것을 확인했다.

그래서 어디서 시간초과가 나는걸까 생각을 하다가 max(value[idx:])에서 나는 것 같았다.

 

즉, 위 코드는 현재 event다음으로 바로 올 수 있는 event의 idx를 이진 탐색을 통해 얻고, idx 부터 끝까지의 value 중 큰 값을 반환하여 answer를 찾는다.

 

하지만 idx부터 끝까지의 value의 max 값을 찾는데 시간초과가 나는 것 같았다.

 

그래서 idx만 주면 max값을 바로 반환하게 할 수 있는 방법이 없을까 고민하다가 다음과 같은 방법을 구현했다.

max_value = [0] * n
max_value[-1] = events[-1][2]

for i in range(n-2, -1, -1):
	max_value[i] = max(max_value[i+1], events[i][2])

.
.
.
.

answer = max(answer, event[2] + max_value[idx])

 

이렇게 하면 max_value[idx]가 max(value[idx:])와 같은 값을 출력하게 된다.

 

---

[LeetCode] 2054. Two Best Non-Overlapping Events