[LeetCode] 2054. Two Best Non-Overlapping Events

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

leetcode - Two Best Non-Overlapping Events

문제 유형: 이진 탐색

문제 난이도: Medium

 

문제

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.

 

0-Indexed의 2D배열 events가 있다. events[i] = startTimei, endTimei, valuei]가 있다.

최대 두 개의 겹치지 않는 events를 골라서, 최대 점수를 얻어보시오.

 

풀이

우선, 시작 지점 기준으로 오름차순 정렬시킨다.

그 뒤, maxPoints[i]를 만든다.

maxPoints[i]는 i인덱스번의 이벤트 이후로 얻을 수 있는 최대 점수를 의미한다.

조건에 맞게 하기 위해, 역방향으로 읽으며 채워주면 된다.

 

각 요소를 돌면서, 이진 탐색을 이용해서 현재 요소의 종료시간보다 큰 시작시간을 찾아서 그 최대 포인트를 구한다.

그 최대값을 갱신해본다.

단, 최대 2개라 했으므로, 1개만 고르는 경우도 고려애햐 한다.

 

최종 답을 반환한다.

 

코드

C++

class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        int n = events.size();
        sort(events.begin(), events.end(), [](const auto &a, const auto &b){
            return a[0] < b[0];
        });

        vector<int> maxPoints(n, 0);
        maxPoints[n-1] = events[n-1][2];
        for(int i = n-2; i >= 0; --i) {
            maxPoints[i] = max(maxPoints[i+1], events[i][2]);
        }

        int ans = 0;
        for(int i = 0; i < n; ++i) {
            int nextIdx = -1;
            ans = max(ans, events[i][2]);

            int left = i + 1, right = n - 1;
            while(left <= right) {
                int mid = (left + right) / 2;
                if(events[mid][0] > events[i][1]) {
                    nextIdx = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            if(nextIdx != -1) {
                ans = max(ans, events[i][2] + maxPoints[nextIdx]);
            }
        }
        return ans;
    }
};