Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1751.html
1751. Maximum Number of Events That Can Be Attended II
Level
Hard
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.length1 <= k * events.length <= 10^61 <= startDay_i <= endDay_i <= 10^91 <= value_i <= 10^6
Solution
First sort events according to the end days. Then use dynamic programming. Suppose there are n events. Create a 2D array dp of n rows and k + 1 columns, where dp[i][j] represents the maximum sum of values when considering the first i + 1 events where the maximum number of events that can be attended is j.
For the first event, dp[0][1] = events[0][2]. For the remaining events, first use binary search to find the maximum index of the previous event such that the previous event’s end day is before the current event, and then calculate the value in dp correspondingly.
Finally, return the maximum value in dp.
-
class Solution { public int maxValue(int[][] events, int k) { int maxValue = 0; Arrays.sort(events, new Comparator<int[]>() { public int compare(int[] event1, int[] event2) { return event1[1] - event2[1]; } }); int length = events.length; int[][] dp = new int[length][k + 1]; int[] event0 = events[0]; for (int j = 1; j <= k; j++) { dp[0][j] = event0[2]; maxValue = Math.max(maxValue, dp[0][j]); } for (int i = 1; i < length; i++) { int[] event = events[i]; int startDay = event[0], value = event[2]; int prevIndex = binarySearch(events, startDay); if (prevIndex < 0) { for (int j = 1; j <= k; j++) { dp[i][j] = Math.max(dp[i - 1][j], value); maxValue = Math.max(maxValue, dp[i][j]); } } else { for (int j = 1; j <= k; j++) { dp[i][j] = Math.max(dp[i - 1][j], dp[prevIndex][j - 1] + value); maxValue = Math.max(maxValue, dp[i][j]); } } } return maxValue; } public int binarySearch(int[][] events, int startDay) { if (events[0][1] >= startDay) return -1; int low = 0, high = events.length - 1; while (low < high) { int mid = (high - low + 1) / 2 + low; int endDay = events[mid][1]; if (endDay >= startDay) high = mid - 1; else low = mid; } return low; } } ############ class Solution { public int maxValue(int[][] events, int k) { Arrays.sort(events, (a, b) -> a[1] - b[1]); int n = events.length; int[][] dp = new int[n + 1][k + 1]; for (int i = 0; i < n; ++i) { int s = events[i][0], v = events[i][2]; int h = search(events, s, i); for (int j = 1; j <= k; ++j) { dp[i + 1][j] = Math.max(dp[i][j], dp[h][j - 1] + v); } } return dp[n][k]; } private int search(int[][] events, int x, int n) { int left = 0, right = n; while (left < right) { int mid = (left + right) >> 1; if (events[mid][1] >= x) { right = mid; } else { left = mid + 1; } } return left; } } -
// OJ: https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended-ii/ // Time: O(KNlogN) // Space: O(KN) class Solution { public: int maxValue(vector<vector<int>>& A, int k) { sort(begin(A), end(A)); vector<vector<int>> dp(k + 1, vector<int>(A.size(), -1)); function<int(int, int)> dfs = [&](int k, int i) { if (k == 0 || i >= A.size()) return 0; if (dp[k][i] != -1) return dp[k][i]; int j = upper_bound(begin(A) + i + 1, end(A), A[i][1], [](int t, auto &a) { return a[0] > t; }) - begin(A); return dp[k][i] = max(dfs(k, i + 1), A[i][2] + dfs(k - 1, j)); }; return dfs(k, 0); } }; -
class Solution: def maxValue(self, events: List[List[int]], k: int) -> int: events.sort(key=lambda x: x[1]) n = len(events) dp = [[0] * (k + 1) for _ in range(n + 1)] for i, (s, _, v) in enumerate(events): h = bisect_left(events, s, hi=i, key=lambda x: x[1]) for j in range(1, k + 1): dp[i + 1][j] = max(dp[i][j], dp[h][j - 1] + v) return dp[n][k] -
func maxValue(events [][]int, k int) int { sort.Slice(events, func(i, j int) bool { return events[i][1] < events[j][1] }) n := len(events) dp := make([][]int, n+1) for i := range dp { dp[i] = make([]int, k+1) } for i, event := range events { h := sort.Search(i, func(k int) bool { return events[k][1] >= event[0] }) for j := 1; j <= k; j++ { dp[i+1][j] = max(dp[i][j], dp[h][j-1]+event[2]) } } return dp[n][k] } func max(a, b int) int { if a > b { return a } return b } -
function maxValue(events: number[][], k: number): number { events.sort((a, b) => a[1] - b[1]); const n = events.length; const f: number[][] = new Array(n + 1) .fill(0) .map(() => new Array(k + 1).fill(0)); const search = (x: number, hi: number): number => { let l = 0; let r = hi; while (l < r) { const mid = (l + r) >> 1; if (events[mid][1] >= x) { r = mid; } else { l = mid + 1; } } return l; }; for (let i = 1; i <= n; ++i) { const [st, _, val] = events[i - 1]; const p = search(st, i - 1); for (let j = 1; j <= k; ++j) { f[i][j] = Math.max(f[i - 1][j], f[p][j - 1] + val); } } return f[n][k]; }