LeetCode 2054. Two Best Non-Overlapping Events(JAVA)

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

 

#문제

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-인덱스의 2D 정수 배열 events가 주어집니다. 여기서 events[i] = [startTimei, endTimei, valuei]입니다.i번째 이벤트는 startTimei에 시작해서 endTimei에 종료되며, 이 이벤트에 참석하면 valuei의 가치를 얻게 됩니다.

최대 두 개의 겹치지 않는 이벤트를 선택하여 해당 이벤트들의 가치 합이 최대가 되도록 하세요.

이때 시작 시간과 종료 시간은 포함됩니다. 즉, 하나의 이벤트가 종료되는 시각에 다른 이벤트가 시작되면 두 이벤트는 겹치는 것으로 간주됩니다.구체적으로, 종료 시간이 t인 이벤트에 참석한 경우, 다음 이벤트는 반드시 t + 1 이후에 시작해야 합니다.
최대 가치의 합을 반환하세요.


2 <= events.length <= 10^5
events[i].length == 3
1 <= startTimei <= endTime
i <= 10^9
1 <= valuei <= 10^6

 

class Solution {
    public int maxTwoEvents(int[][] events) {
      
    }
}

 

접근

겹치지 않는 최대2개의 이벤트의 가치합을 최대로 만들어야하는 문제다.

 

최댓값을 구하기위해 각각의 이벤트가 종료된 이후에 발생하는 이벤트중 가장 큰 가치를 구할수있다면 문제에서 요구하는 답을 얻을수있을것이다.

 

이를 정렬과 이분탐색을 이용하여 작성했다.

 

정렬

Arrays.sort(events, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));

 

이벤트의 시작시간과 종료시간을 기준으로 정렬해주었다.

 

 

특정 이벤트부터  나올 수 있는 가장 큰 가치 구하기

int[] arr = new int[n];
arr[n-1] = events[n-1][2];
//i번째 이벤트부터 나올수있는 최대 value
for (int i = n-2; i >= 0; i--) {
    arr[i] = Math.max(events[i][2], arr[i+1]);
}

n번째 이벤트부터 역순으로 진행하면서 i번째 이벤트 부터 나올수있는 최대가치를 담는 arr를 선언하고 값을 할당해주었다.

 

이분탐색

for (int i = 0; i < n; i++) {
    int left = i+1, right = n-1;
    int nextEvt = -1;
    //현재 인벤트 종료후에 나오는 다음 이벤트의 위치를 찾는다. 즉 겹치지않는 다음이벤트
    while (left <= right) {
        int mid = (left + right) / 2;
        if (events[mid][0] > events[i][1]) {
            right = mid-1;
            nextEvt = mid;
        }else{
            left = mid+1;
        }
    }
    if (nextEvt == -1) {//다음 이벤트가 없다면
        //현재 이벤트의 value를 최댓값
        max = Math.max(max, events[i][2]);
    }else{
        max = Math.max(max, events[i][2] + arr[nextEvt]);
    }
}

현재의 이벤트가 i번째라고했을때 이분탐색을 통해 i번째 이벤트가 종료된 이후에 첫번째로 발생하는 이벤트의 위치를 찾는다.  이후 max값을 업데이트 해나가면 된다.

 

전체코드

class Solution {
    public int maxTwoEvents(int[][] events) {
        int max = Integer.MIN_VALUE;
        int n = events.length;
        Arrays.sort(events, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
        int[] arr = new int[n];
        arr[n-1] = events[n-1][2];
        //i번째 이벤트 이후에 나올수있는 최대 value
        for (int i = n-2; i >= 0; i--) {
            arr[i] = Math.max(events[i][2], arr[i+1]);
        }
        for (int i = 0; i < n; i++) {
            int left = i+1, right = n-1;
            int nextEvt = -1;
            //현재 인벤트 종료후에 나오는 다음 이벤트의 위치를 찾는다. 즉 겹치지않는 다음이벤트
            while (left <= right) {
                int mid = (left + right) / 2;
                if (events[mid][0] > events[i][1]) {
                    right = mid-1;
                    nextEvt = mid;
                }else{
                    left = mid+1;
                }
            }
            if (nextEvt == -1) {//다음 이벤트가 없다면
                //현재 이벤트의 value를 최댓값
                max = Math.max(max, events[i][2]);
            }else{
                max = Math.max(max, events[i][2] + arr[nextEvt]);
            }
        }

        return max;
    }
}

 

이 문제는 다양한 풀이법을 가지고 있는데, 대표적으로 우선순위 큐를 이용한 방법과 다이나믹 프로그래밍(DP) + 재귀를 활용한 방식이 있다. 우선순위 큐를 활용한 풀이는 비교적 직관적이고 위에서 설명한 방식과 유사하게 접근할 수 있어 이해하기 쉬웠지만.

 

다이나믹 프로그래밍(DP) + 재귀 방식은 개인적으로 아직 해당 방식에 대한 이해와 실력이 부족해 코드를 봐도 진행과정을 머릿속으로 그리지못해 아쉽게도 자세히 다루지 못했다.  앞으로 이런 방식을 완전히 이해하고 활용할 수 있도록 더 노력해야할거같다.