{x}
blog image

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.

 

Constraints:

  • 1 <= k <= events.length
  • 1 <= k * events.length <= 106
  • 1 <= startDayi <= endDayi <= 109
  • 1 <= valuei <= 106

Problem: Maximum Number of Events That Can Be Attended II

This problem asks to find the maximum sum of values that can be received by attending events, given constraints on the number of events that can be attended and event overlaps.

Approach

The problem can be solved using dynamic programming. We'll sort the events by their end times. This allows for efficient searching for non-overlapping events. We'll use a DP table dp[i][j] to represent the maximum value achievable by attending at most j events from the first i events.

Detailed Explanation with Code (Python)

import bisect
 
class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        #Sort events by end time
        events.sort(key=lambda x: x[1])
        n = len(events)
        
        # dp[i][j] : max value attending at most j events from first i events
        dp = [[0] * (k + 1) for _ in range(n + 1)]
 
        for i in range(1, n + 1):
            start, end, value = events[i - 1]
            
            # Find the index of the last event that doesn't overlap with the current event.
            # bisect_left finds the insertion point for `start` in the sorted `events` array up to index `i-1`.
            prev_event_index = bisect.bisect_left([event[1] for event in events[:i-1]], start)
 
            for j in range(1, k + 1):
                #Option 1: Don't attend current event.
                dp[i][j] = dp[i-1][j]
                
                #Option 2: Attend the current event if possible
                if j > 0:
                    dp[i][j] = max(dp[i][j], dp[prev_event_index][j - 1] + value)
 
        return dp[n][k]

Time Complexity Analysis:

  • Sorting events takes O(N log N) time, where N is the number of events.
  • The nested loops iterate through O(N * K) combinations.
  • The bisect_left operation takes O(log N) time in each inner loop iteration. However, the overall time complexity remains dominated by O(N*K).

Therefore, the overall time complexity is O(N log N + N * K). If K is significantly smaller than N, this is approximately O(N log N).

Space Complexity Analysis:

The space complexity is dominated by the DP table, which has dimensions (N+1) x (K+1). Thus, the space complexity is O(N*K).

Other Languages

The logic remains consistent across different programming languages. The primary differences lie in the syntax and specific functions used for sorting and binary search. The provided solutions in Java, C++, and Go reflect these variations while maintaining the core dynamic programming approach. The time and space complexity remain the same as in the Python solution.