[JAVA 문제 풀이] 369. Maximum Number of Events That Can Be Attended II (참석할 수 있는 최대 이벤트 수 II)

Maximum Number of Events That Can Be Attended II - LeetCode

Can you solve this real interview question? Maximum Number of Events That Can Be Attended II - You are given an array of events where events[i] = [startDayi, endDayi, valuei]. The ith event starts at startDayi and ends at endDayi, and if you attend this event, you will receive a value of valuei. You are also given an integer k which represents the maximum number of events you can attend. You can only attend one event at a time. If you choose to attend an event, you must attend the entire event. Note that the end day is inclusive: that is, you cannot attend two events where one of them starts and the other ends on the same day. Return the maximum sum of values that you can receive by attending events.   Example 1: [https://assets.leetcode.com/uploads/2021/01/10/screenshot-2021-01-11-at-60048-pm.png] Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2 Output: 7 Explanation: Choose the green events, 0 and 1 (0-indexed) for a total value of 4 + 3 = 7. Example 2: [https://assets.leetcode.com/uploads/2021/01/10/screenshot-2021-01-11-at-60150-pm.png] Input: events = [[1,2,4],[3,4,3],[2,3,10]], k = 2 Output: 10 Explanation: Choose event 2 for a total value of 10. Notice that you cannot attend any other event as they overlap, and that you do not have to attend k events. Example 3: [https://assets.leetcode.com/uploads/2021/01/10/screenshot-2021-01-11-at-60703-pm.png] Input: events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3 Output: 9 Explanation: Although the events do not overlap, you can only attend 3 events. Pick the highest valued three.   Constraints: * 1 <= k <= events.length * 1 <= k * events.length <= 106 * 1 <= startDayi <= endDayi <= 109 * 1 <= valuei <= 106

https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended-ii/description/

events[i] = [startDayi, endDayi, valuei]인 다양한 이벤트가 제공됩니다.
i번째 이벤트는 startDayi에서 시작하여 endDayi에서 종료되며,
이 이벤트에 참석하면 valuei 값을 받게 됩니다.
또한 참석할 수 있는 최대 이벤트 수를 나타내는 정수 k가 주어집니다.

한 번에 하나의 이벤트에만 참석할 수 있습니다.
이벤트에 참석하기로 선택한 경우 전체 이벤트에 참석해야 합니다.
단, 하나는 시작하고 다른 하나는 같은 날 끝나는 두 이벤트에는 참석할 수 없습니다.

행사에 참석하여 받을 수 있는 최대 값의 합계를 반환하세요.

제약 조건:
* 1 <= k <= events.length
* 1 <= k * events.length <= 10^6
* 1 <= startDayi <= endDayi <= 10^9
* 1 <= valuei <= 10^6

내가 작성한 코드 + 다른 사람의 코드

import java.util.*;

class Solution {
    public int maxValue(int[][] events, int k) {
        int n = events.length;

        // 종료일 기준 정렬
        Arrays.sort(events, (a, b) -> a[1] - b[1]);

        // dp[i][j] = i번째 이벤트까지 고려했을 때 j개의 이벤트를 선택한 최대 값
        int[][] dp = new int[n + 1][k + 1];

        // dp 초기화
        for (int i = 1; i <= n; i++) {
            int[] curr = events[i - 1]; // i번째 이벤트
            int start = curr[0]; // 시작일
            int value = curr[2]; // 가치

            // 이전 겹치지 않는 이벤트 index 찾기
            int idx = binarySearch(events, start);

						// 아래 텍스트 필드 설명 참고
            for (int j = 1; j <= k; j++) {
                // 안 고름
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);

                // 고름 (이전 겹치지 않는 이벤트까지 고려)
                dp[i][j] = Math.max(dp[i][j], dp[idx + 1][j - 1] + value);
            }
        }

        return dp[n][k];
    }

    // 가장 가까운 end <= start - 1인 index를 찾음
    private int binarySearch(int[][] events, int start) {
        int left = 0;
        int right = events.length - 1;
        int res = -1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (events[mid][1] < start) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return res;
    }
}

dp[i][j]는 항상
i번째 이벤트까지 고려했을 때
j개의 이벤트를 선택한 최대 값을 가지게 됨
(j개 보다 적게 선택한 값이 최대값일 경우 해당 값을 가져옴)

EX) events = [[1,2,4],[2,3,10],[3,4,3]], k = 2
3일차에서 2개 선택한 이벤트의 가치(7)가
2일차 1개 선택한 이벤트의 가치(10)을 계승함

DP(Dynamic Programming) [동적 계획법] - stupefyee

기술정리

https://stupefyee.inblog.io/dpdynamic-programming-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95-60377?traffic_type=internal