Maximum Number of Events That Can Be Attended - Problem

You are given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.

You can attend an event i at any day d where startDayi ≤ d ≤ endDayi. You can only attend one event at any time d.

Return the maximum number of events you can attend.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: We can attend all three events: attend event [1,2] on day 1, event [2,3] on day 2, and event [3,4] on day 3.

Example 2 — Overlapping Events

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

› Output: 4

💡 Note: We can attend all four events: attend first [1,2] on day 1, [2,3] on day 2, [3,4] on day 3, and second [1,2] on day 2. Wait, that's wrong - we can't attend two events on day 2. Actually, we attend first [1,2] on day 1, second [1,2] on day 2, [2,3] on day 3, and [3,4] on day 4.

Example 3 — Single Day Events

$ Input: events = [[1,4],[4,4],[1,4],[1,4]]

› Output: 4

💡 Note: We can attend event [1,4] on days 1, 2, 3, and the [4,4] event on day 4, for a total of 4 events.

Constraints

1 ≤ events.length ≤ 10⁵
events[i].length == 2
1 ≤ startDay_i ≤ endDay_i ≤ 10⁵

Visualization

Tap to expand

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use a greedy approach: always attend events that end earliest to maximize future opportunities. Best approach is Sort by End Time - sort events by end time and greedily select non-conflicting events. Time: O(n log n), Space: O(1)

Common Approaches

✓ Backtracking

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

Brute Force - Try All Combinations

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

Try every possible combination of events (2^n subsets) and check if they can be attended without conflicts. Return the size of the largest valid combination.

Greedy with Priority Queue

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

Process events chronologically. For each day, add all starting events to a priority queue ordered by end time. Always attend the event ending soonest to maximize future opportunities.

Sort by End Time

⏱️ Time: O(n log n) Space: O(1)

Sort all events by their end time, then iterate through them and select events that don't conflict with previously selected ones. This ensures we always pick events that end earliest.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

static int events[10000][2];
static int pq[10000];
static int pqSize = 0;

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

void pqPush(int val) {
    pq[pqSize] = val;
    int pos = pqSize;
    pqSize++;
    
    // Bubble up
    while (pos > 0) {
        int parent = (pos - 1) / 2;
        if (pq[parent] <= pq[pos]) break;
        int temp = pq[parent];
        pq[parent] = pq[pos];
        pq[pos] = temp;
        pos = parent;
    }
}

int pqPop() {
    if (pqSize == 0) return -1;
    
    int result = pq[0];
    pqSize--;
    if (pqSize == 0) return result;
    
    pq[0] = pq[pqSize];
    int pos = 0;
    
    // Bubble down
    while (1) {
        int left = 2 * pos + 1;
        int right = 2 * pos + 2;
        int smallest = pos;
        
        if (left < pqSize && pq[left] < pq[smallest]) {
            smallest = left;
        }
        if (right < pqSize && pq[right] < pq[smallest]) {
            smallest = right;
        }
        
        if (smallest == pos) break;
        
        int temp = pq[pos];
        pq[pos] = pq[smallest];
        pq[smallest] = temp;
        pos = smallest;
    }
    
    return result;
}

int pqPeek() {
    if (pqSize == 0) return -1;
    return pq[0];
}

int pqIsEmpty() {
    return pqSize == 0;
}

int solution(int eventCount) {
    // Sort events by end day
    qsort(events, eventCount, sizeof(int[2]), compare);
    
    // Use greedy approach with priority queue
    pqSize = 0; // Reset priority queue
    int maxDay = 0;
    for (int i = 0; i < eventCount; i++) {
        if (events[i][1] > maxDay) {
            maxDay = events[i][1];
        }
    }
    
    int count = 0;
    int eventIndex = 0;
    
    // Process each day
    for (int day = 1; day <= maxDay; day++) {
        // Add all events that start today or before
        while (eventIndex < eventCount && events[eventIndex][0] <= day) {
            // Only add if event hasn't ended
            if (events[eventIndex][1] >= day) {
                pqPush(events[eventIndex][1]);
            }
            eventIndex++;
        }
        
        // Remove events that have ended
        while (!pqIsEmpty() && pqPeek() < day) {
            pqPop();
        }
        
        // Attend the event that ends earliest (if any)
        if (!pqIsEmpty()) {
            pqPop();
            count++;
        }
    }
    
    return count;
}

int parse2DArray(char* input) {
    if (strcmp(input, "[]") == 0) {
        return 0;
    }
    
    int eventCount = 0;
    char* ptr = input;
    
    while (*ptr) {
        if (*ptr == '[') {
            ptr++; // Skip '['
            
            // Parse first number
            while (*ptr && !isdigit(*ptr) && *ptr != '-') ptr++;
            if (!*ptr) break;
            
            char* endPtr;
            events[eventCount][0] = (int)strtol(ptr, &endPtr, 10);
            ptr = endPtr;
            
            // Skip to next number
            while (*ptr && !isdigit(*ptr) && *ptr != '-') ptr++;
            if (!*ptr) break;
            
            events[eventCount][1] = (int)strtol(ptr, &endPtr, 10);
            ptr = endPtr;
            
            eventCount++;
            
            // Skip to next '[' or end
            while (*ptr && *ptr != '[') ptr++;
        } else {
            ptr++;
        }
    }
    
    return eventCount;
}

int main() {
    char line[10000];
    
    fgets(line, sizeof(line), stdin);
    
    // Remove newline
    int len = strlen(line);
    if (len > 0 && line[len-1] == '\n') {
        line[len-1] = '\0';
    }
    
    int eventCount = parse2DArray(line);
    
    int result = solution(eventCount);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 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