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

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

✓ Optimized

⏱️ Time: N/A Space: N/A

2D Dynamic Programming with Binary Search

⏱️ Time: O(n log n + n × k) Space: O(n × k)

Sort events by end time, then use a 2D DP table where dp[i][j] represents maximum value using first i events with at most j events selected. Use binary search to efficiently find the next non-overlapping event.

Brute Force Recursion

⏱️ Time: O(2^n) Space: O(n)

For each event, we have two choices: attend it or skip it. If we attend, we add its value and recursively solve for remaining events that don't overlap. We try all combinations and return the maximum.

Dynamic Programming with Memoization

⏱️ Time: O(n² × k) Space: O(n × k)

Same recursive approach as brute force, but we cache results for each (index, remaining_k) state to avoid recalculating the same subproblems multiple times.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

typedef struct {
    int start;
    int end;
    int value;
} Event;

typedef struct {
    int i;
    int remaining;
    int result;
} MemoEntry;

MemoEntry memo[1010][1010];
bool memoSet[1010][1010];

int compare(const void* a, const void* b) {
    Event* ea = (Event*)a;
    Event* eb = (Event*)b;
    return ea->start - eb->start;
}

int dfs(Event* events, int n, int i, int remaining) {
    if (i >= n || remaining == 0) {
        return 0;
    }
    
    if (memoSet[i][remaining]) {
        return memo[i][remaining].result;
    }
    
    // Skip current event
    int maxVal = dfs(events, n, i + 1, remaining);
    
    // Take current event and find next non-overlapping
    int currentEnd = events[i].end;
    int nextIdx = n;
    for (int j = i + 1; j < n; j++) {
        if (events[j].start > currentEnd) {
            nextIdx = j;
            break;
        }
    }
    
    int takeVal = events[i].value + dfs(events, n, nextIdx, remaining - 1);
    if (takeVal > maxVal) {
        maxVal = takeVal;
    }
    
    memo[i][remaining].result = maxVal;
    memoSet[i][remaining] = true;
    return maxVal;
}

int solution(Event* events, int n, int k) {
    qsort(events, n, sizeof(Event), compare);
    memset(memoSet, false, sizeof(memoSet));
    return dfs(events, n, 0, k);
}

void parseEvents(const char* str, Event* events, int* count) {
    *count = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',' || *p == '[') p++;
        if (*p == ']' || *p == '\0') break;
        
        events[*count].start = (int)strtol(p, (char**)&p, 10);
        while (*p == ',' || *p == ' ') p++;
        events[*count].end = (int)strtol(p, (char**)&p, 10);
        while (*p == ',' || *p == ' ') p++;
        events[*count].value = (int)strtol(p, (char**)&p, 10);
        while (*p == ']' || *p == ' ') p++;
        
        (*count)++;
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    Event events[1000];
    int n = 0;
    parseEvents(line, events, &n);
    
    fgets(line, sizeof(line), stdin);
    int k = atoi(line);
    
    int result = solution(events, n, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

⚡ Linearithmic

Space Complexity

⚡ 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