(Python3) - LeetCode (Medium) : 2054. Two Best Non-Overlapping Events

https://leetcode.com/problems/two-best-non-overlapping-events/description

dp와 binary search 를 사용해본 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. end_time에 대해 events를 오름차순으로 정렬합니다.

 

2. i번째 까지 event를 선택하거나 선택하지 않은 경우의 최댓값을 저장할 max_values_until_current_event를 선언 후 events길이만큼 저장해줍니다.

 

3. end_times를 따로 events에서 추출해 배열로 저장해줍니다.

📔 풀이과정

1. 이벤트 정렬: endTime 기준으로 정렬. 이렇게 하면 과거의 이벤트들 중 겹치지 않는 마지막 이벤트를 빠르게 찾을 수 있습니다.
2. max_values_until_current_event를 갱신:
    - 인덱스 i까지의 이벤트에서 최대 값을 누적 저장.
    - max_values_until_current_event[i] = max(max_values_until_current_event[i-1], events[i][2])

 

3. 이진 탐색으로 겹치지 않는 이벤트 찾기:
    - 현재 이벤트의 start_time보다 작은 end_time을 가진 마지막 이벤트를 찾아줍니다. 이는 end_times에서 start_time이 lower_bound를 찾은 뒤 - 1한 index를 찾아주면 됩니다.

4. 최대 합 계산:
    - current_value +max_values_until_current_event[idx]: 현재 이벤트와 겹치지 않는 최대 값의 합
    - max_sum을 갱신

📔 정답 출력 | 반환

max_sum을 반환합니다.

---

📕 Code

📔 Python3

from bisect import bisect_left

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        events.sort(key=lambda x: x[1])
        max_values_until_current_event = [0]*len(events)
        max_values_until_current_event[0] = events[0][2]

        for i in range(1, len(events)):
            max_values_until_current_event[i] = max(max_values_until_current_event[i-1], events[i][2])
        max_sum = 0
        end_times = [event[1] for event in events]

        for i in range(len(events)):
            current_value = events[i][2]
            start_time = events[i][0]
            non_intersect_idx = bisect_left(end_times, start_time) - 1
            if non_intersect_idx >= 0:
                max_sum = max(max_sum,max_values_until_current_event[non_intersect_idx] + current_value)
            else:
                max_sum = max(max_sum, current_value )
        return max_sum

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.