1751. Maximum Number of Events That Can Be Attended II LeetCode Solution
In this guide, you will get 1751. Maximum Number of Events That Can Be Attended II LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Events That Can Be Attended II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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:
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.
1751. Maximum Number of Events That Can Be Attended II LeetCode Solution in C++
class Solution {
public:
int maxValue(vector<vector<int>>& events, int k) {
vector<vector<int>> mem(events.size(), vector<int>(k + 1, -1));
ranges::sort(events);
return maxValue(events, 0, k, mem);
}
private:
// Returns the maximum sum of values that you can receive by attending
// events[i..n), where k is the maximum number of attendancevents.
int maxValue(const vector<vector<int>>& events, int i, int k,
vector<vector<int>>& mem) {
if (k == 0 || i == events.size())
return 0;
if (mem[i][k] != -1)
return mem[i][k];
// Binary search `events` to find the first index j
// s.t. events[j][0] > events[i][1].
const auto it = upper_bound(
events.begin() + i, events.end(), events[i][1],
[](int end, const vector<int>& event) { return event[0] > end; });
const int j = distance(events.begin(), it);
return mem[i][k] = max(events[i][2] + maxValue(events, j, k - 1, mem),
maxValue(events, i + 1, k, mem));
}
}; /* code provided by PROGIEZ */
1751. Maximum Number of Events That Can Be Attended II LeetCode Solution in Java
class Solution {
public int maxValue(int[][] events, int k) {
Integer[][] mem = new Integer[events.length][k + 1];
Arrays.sort(events,
(a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
return maxValue(events, 0, k, mem);
}
private int maxValue(int[][] events, int i, int k, Integer[][] mem) {
if (k == 0 || i == events.length)
return 0;
if (mem[i][k] != null)
return mem[i][k];
// Binary search `events` to find the first index j
// s.t. events[j][0] > events[i][1].
final int j = firstGreaterEqual(events, i + 1, events[i][1] + 1);
return mem[i][k] = Math.max(events[i][2] + maxValue(events, j, k - 1, mem),
maxValue(events, i + 1, k, mem));
}
// Finds the first index l s.t events[l][0] >= target.
private int firstGreaterEqual(int[][] events, int l, int target) {
int r = events.length;
while (l < r) {
final int m = (l + r) / 2;
if (events[m][0] >= target)
r = m;
else
l = m + 1;
}
return l;
}
} // code provided by PROGIEZ
1751. Maximum Number of Events That Can Be Attended II LeetCode Solution in Python
class Solution:
def maxValue(self, events: list[list[int]], k: int) -> int:
events.sort()
@functools.lru_cache(None)
def dp(i: int, k: int) -> int:
"""
Returns the maximum sum of values that you can receive by attending
events[i..n), where k is the maximum number of attendance.
"""
if k == 0 or i == len(events):
return 0
# Binary search `events` to find the first index j
# s.t. events[j][0] > events[i][1].
j = bisect.bisect(events, [events[i][1], math.inf, math.inf], i + 1)
return max(events[i][2] + dp(j, k - 1), dp(i + 1, k))
return dp(0, k) # code by PROGIEZ
