Maximum Number of Events That Can Be Attended II

Maximum Number of Events That Can Be Attended II - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2

› Output: 7

💡 Note: Choose events [1,2,4] and [3,4,3]. Event [1,2,4] ends at day 2 and [3,4,3] starts at day 3, so no overlap. Total value = 4 + 3 = 7.

Example 2 — Single Event

$ Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 1

› Output: 4

💡 Note: Can only attend one event. Choose the highest value event [1,2,4] with value 4.

Example 3 — All Overlapping

$ Input: events = [[1,1,1],[2,2,2],[3,3,3]], k = 3

› Output: 6

💡 Note: No events overlap since each lasts only one day. Can attend all three: 1 + 2 + 3 = 6.

Constraints

1 ≤ events.length ≤ 10⁶
events[i].length == 3
1 ≤ startDayi ≤ endDayi ≤ 10⁹
1 ≤ valuei ≤ 10⁶
1 ≤ k ≤ min(events.length, 10⁶)

Visualization

Tap to expand

Understanding the Visualization

Input

Events with [start, end, value] and limit k=2

Process

Sort by end time, use DP to find optimal selection

Output

Maximum value from selected events

Key Takeaway

🎯 Key Insight: Sort events by end time, then use dynamic programming to choose the optimal combination of non-overlapping events within the limit k.

Asked in

G Google 15 f Facebook 12 a Amazon 10

The key insight is to sort events by end time and use dynamic programming to track the maximum value achievable. For each event, we decide whether to attend it (and find the previous compatible event) or skip it. The optimal approach uses a 2D DP table with binary search for O(n log n + n×k) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ 2D Dynamic Programming with Binary Search	O(n log n + n × k)	O(n × k)	Sort events by end time and use DP table with binary search for optimal performance
Brute Force Recursion	O(2^n)	O(n)	Try all possible combinations of events using recursion
Dynamic Programming with Memoization	O(n² × k)	O(n × k)	Use recursion with caching to avoid redundant calculations

2D Dynamic Programming with Binary Search — Algorithm Steps

Sort events by end time
Create DP table dp[i][j] for i events, j selections
For each event, decide to take or skip
Use binary search to find next valid event after current
Fill DP table bottom-up

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort

Sort events by end time

DP Table

Fill dp[i][j] for i events, j selections

Optimal

dp[n][k] contains maximum value

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    int* eventA = (int*)a;
    int* eventB = (int*)b;
    return eventA[1] - eventB[1];
}

int solution(int events[][3], int n, int k) {
    // Sort events by end time
    qsort(events, n, sizeof(events[0]), compare);
    
    // DP table: dp[i][j] = max value using first i events with at most j selections
    int dp[1001][1001] = {0};
    
    for (int i = 1; i <= n; i++) {
        int start = events[i - 1][0];
        int value = events[i - 1][2];
        
        for (int j = 1; j <= k; j++) {
            // Option 1: Skip current event
            dp[i][j] = dp[i - 1][j];
            
            // Option 2: Take current event
            // Find last event that ends before current starts
            int prevIdx = 0;
            for (int p = 0; p < i - 1; p++) {
                if (events[p][1] < start) {
                    prevIdx = p + 1;
                }
            }
            
            int takeValue = value + dp[prevIdx][j - 1];
            if (takeValue > dp[i][j]) {
                dp[i][j] = takeValue;
            }
        }
    }
    
    return dp[n][k];
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int events[1000][3];
    int n = 0;
    
    char* ptr = strchr(line, '[');
    ptr++;
    
    while (*ptr != ']' && n < 1000) {
        if (*ptr == '[') {
            ptr++;
            events[n][0] = strtol(ptr, &ptr, 10);
            ptr++;
            events[n][1] = strtol(ptr, &ptr, 10);
            ptr++;
            events[n][2] = strtol(ptr, &ptr, 10);
            n++;
            while (*ptr != ']' && *ptr != '\0') ptr++;
            if (*ptr == ']') ptr++;
            if (*ptr == ',') ptr++;
        } else {
            ptr++;
        }
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(events, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + n × k)

O(n log n) for sorting, then O(n × k) for DP table filling with O(log n) binary search per cell

⚡ Linearithmic

Space Complexity

O(n × k)

2D DP table stores results for n events and k selections

⚡ Linearithmic Space

89.4K Views

Medium Frequency

~35 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

2D Dynamic Programming with Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler