[LeetCode 1751] Maximum Number of Events That Can Be Attended II

문제 바로가기

Description

---

You are given an array of events where events[i] = [startDay_i, endDay_i, value_i]. The i^th event starts at startDay_i and ends at endDay_i, and if you attend this event, you will receive a value of value_i. 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

---

• 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

---

• 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

---

• 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 <= 10^6
• 1 <= startDay_i <= endDay_i <= 10^9
• 1 <= value_i <= 10^6

Hint

---

Hint 1

  Sort the events by its startTime.
	

Hint 2

  For every event, you can either choose it and consider the next event available, or you can ignore it. You can efficiently find the next event that is available using binary search.
	

Code

---

내 제출

---

class Solution {
    private int[][] events;
    private int[][] f;
    private int n;

    public int maxValue(int[][] events, int k) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        this.events = events;
        n = events.length;
        f = new int[n][k + 1];
        return dfs(0, k);
    }

    private int dfs(int i, int k) {
        if (i >= n || k <= 0) {
            return 0;
        }
        if (f[i][k] != 0) {
            return f[i][k];
        }
        int j = search(events, events[i][1], i + 1);
        int ans = Math.max(dfs(i + 1, k), dfs(j, k - 1) + events[i][2]);
        return f[i][k] = ans;
    }

    private int search(int[][] events, int x, int lo) {
        int l = lo, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (events[mid][0] > x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

Runtime	Memory
65 ms	133.5 MB

다른 풀이

---

import java.util.*;

class Solution {
    int[][] dp;

    public int maxValue(int[][] events, int k) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        dp = new int[events.length][k + 1];

        for (int[] row : dp) Arrays.fill(row, -1);

        return solve(events, 0, k);
    }

    private int solve(int[][] events, int i, int k) {
        if (i == events.length || k == 0) return 0;

        if (dp[i][k] != -1) return dp[i][k];

        int skip = solve(events, i + 1, k);

        int next = binarySearch(events, events[i][1]);
        int take = events[i][2] + solve(events, next, k - 1);

        return dp[i][k] = Math.max(skip, take);
    }

    private int binarySearch(int[][] events, int endTime) {
        int left = 0, right = events.length;

        while (left < right) {
            int mid = (left + right) / 2;
            if (events[mid][0] <= endTime) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/1700-1799/1751.Maximum%20Number%20of%20Events%20That%20Can%20Be%20Attended%20II/Solution.java