Maximum Number of Events That Can Be Attended

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

Understanding the Visualization

Input Events

Array of events with [start_day, end_day] ranges

Apply Strategy

Use greedy approach to select optimal events

Count Attended

Return maximum number of events we can attend

Key Takeaway

🎯 Key Insight: Greedy approach works - always attend events ending earliest to leave maximum room for future events

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

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^n × n²)	O(n)	Generate all possible subsets of events and find the maximum valid combination
Greedy with Priority Queue	O(n log n + d × log n)	O(n)	Sort events by start time, use min-heap to always attend events ending soonest
Sort by End Time	O(n log n)	O(1)	Sort events by end time and greedily select non-overlapping events

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible subsets of events
For each subset, check if events can be attended without conflicts
Return the maximum size among valid subsets

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all 2^n possible combinations of events

Validate Each

Check if events in each subset can be attended without conflicts

Find Maximum

Return the size of the largest valid combination

Code -

solution.c — C

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

bool isValidCombination(int events[][2], int count) {
    int dayToEvent[10000] = {0}; // Assuming max day <= 10000
    
    for (int i = 0; i < count; i++) {
        int start = events[i][0], end = events[i][1];
        bool found = false;
        for (int day = start; day <= end; day++) {
            if (!dayToEvent[day]) {
                dayToEvent[day] = 1;
                found = true;
                break;
            }
        }
        if (!found) {
            return false;
        }
    }
    
    return true;
}

int solution(int events[][2], int n) {
    int maxEvents = 0;
    
    // Try all possible subsets (2^n combinations)
    for (int mask = 0; mask < (1 << n); mask++) {
        int selected[20][2]; // Assuming n <= 20 for brute force
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                selected[count][0] = events[i][0];
                selected[count][1] = events[i][1];
                count++;
            }
        }
        
        // Check if this combination is valid
        if (isValidCombination(selected, count)) {
            if (count > maxEvents) {
                maxEvents = count;
            }
        }
    }
    
    return maxEvents;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[1,2],[3,4]] format
    int events[20][2];
    int n = 0;
    
    char* ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            events[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            if (*ptr == ',') ptr++;
            events[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr == ']') ptr++;
            n++;
        } else {
            ptr++;
        }
    }
    
    int result = solution(events, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n²)

2^n subsets, each requiring O(n²) validation for conflicts

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack and temporary storage for subsets

⚡ Linearithmic 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler