2054. Two Best Non-Overlapping Events

문제

You are given a 0-indexed 2D integer array of events where events[i] = [startTimei, endTimei, valuei]. 
The ith event starts at startTimei and ends at endTimei, and if you attend this event, 
you will receive a value of valuei. 
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.

• 시작시간, 끝시간, 값 으로 이벤트의 시간표가 주어진다.
• 이 이벤트를 성공적으로 마치면 주어진 값 만큼의 보상을 얻는다.
• 최대 2개의 이벤트를 진행할때 얻을수 있는 최대의 보상을 구하여라
  • 단, 이벤트의 시간은 겹쳐선 안된다.
  • 1시에 시작해서 2시에 끝나는 이벤트가 있으면, 최소 3시에 시작하는 이벤트를 골라야 함

예제

[[1,3,2],[4,5,2],[2,4,3]]

• 2짜리 2개를 선택하는것이 가장 유리하다.

제한

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

풀이

1. 먼저 1개만 고를때의 최댓값을 찾는다.
2. 그 이후 오름차순 정렬후 거꾸로 뒤집어서 특정 시간 이후 모든 이벤트들의 최대 값을
   모노토닉 스택으로 기록한다.
3. 끝나는 시간으로 오름차순 정렬 후 모노토닉 스택을 활용해 두개의 이벤트를 고를때 최선의 답을 찾는다.

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        _, _, ans = max(events, key=lambda k: k[2])

        events.sort()

        q = []

        for start, _, value in reversed(events):
            if not q or q[-1][1] < value:
                q.append((start, value))

        events.sort(key=lambda k: k[1])

        for _, end, value in events:
            while q and end >= q[-1][0]:
                q.pop()
            if not q:
                return ans
            else:
                largest = q[-1][1]
                ans = max(value + largest, ans)

        return ans