Maximum Number of Events That Can Be Attended

MediumIntervals · Greedy · Heap (Priority Queue)🧩 Intervals & Line Sweep LeetCode #1353 ↗Updated Oct 30, 2026

Problem

Each events[i] = [startDay, endDay] can be attended on any single day d with startDay ≤ d ≤ endDay. You can attend at most one event per day. Return the maximum number of events you can attend.

Inputevents = [[1,2],[2,3],[3,4]]Output3

Inputevents = [[1,2],[2,3],[3,4],[1,2]]Output4

Inputevents = [[1,1],[1,1],[1,1]]Output1

1 ≤ events.length ≤ 10⁵ · 1 ≤ startDay ≤ endDay ≤ 10⁵

Try it yourself

Java

class Solution {
    public int maxEvents(int[][] events) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

On any given day, among the events that are already open, attend the one whose deadline is soonest — the others can still wait. A min-heap of end days, filled as days advance, answers “which deadline is next?” instantly.

PatternIntervals & Line Sweep

Instinct See [start, end] pairs, meetings, bookings or the word "overlap"? Sort by an endpoint, then sweep left to right carrying one running fact.

Memory hack Sort, then sweep - start time to merge, end time to choose, +1/-1 events to count the crowd.

Open the Intervals & Line Sweep guide →

Approaches

Brute ForceBacktracking over Day Assignments

Time O((D+1)ⁿ)Space O(n + D)

For each event, either skip it or place it on any still-free day inside its range, then recurse on the next event. Exploring every assignment guarantees the maximum is found (D = largest end day).

Java

public int maxEvents(int[][] events) {
    int maxDay = 0;
    for (int[] e : events) maxDay = Math.max(maxDay, e[1]);
    return assign(events, 0, new boolean[maxDay + 1]);
}

private int assign(int[][] events, int i, boolean[] used) {
    if (i == events.length) return 0;
    int best = assign(events, i + 1, used); // skip event i
    for (int d = events[i][0]; d <= events[i][1]; d++) {
        if (!used[d]) {
            used[d] = true;
            best = Math.max(best, 1 + assign(events, i + 1, used));
            used[d] = false;
        }
    }
    return best;
}

A correct reference for tiny inputs; hopelessly exponential otherwise.

BetterEarliest Deadline First + Day Scan

Time O(n log n + n·D)Space O(D)

Sort events by end day. Handle them in that order and give each one the earliest free day in its range. An exchange argument shows this never hurts: an event that ends sooner has fewer options, so it should claim first, and taking the earliest day leaves later days for later deadlines.

Java

public int maxEvents(int[][] events) {
    Arrays.sort(events, (a, b) -> Integer.compare(a[1], b[1])); // soonest deadline first
    int maxDay = events[events.length - 1][1];
    boolean[] used = new boolean[maxDay + 1];
    int attended = 0;
    for (int[] e : events) {
        for (int d = e[0]; d <= e[1]; d++) {
            if (!used[d]) { // earliest free day inside the window
                used[d] = true;
                attended++;
                break;
            }
        }
    }
    return attended;
}

Polynomial and simple, but scanning for a free day can cost O(D) per event.

OptimalDay Sweep with Min-Heap of End Days

Time O(n log n)Space O(n)

Sort by start day and walk forward in time. Each day, push the end days of events that open today, discard ends that already passed, then attend the event with the smallest end. When nothing is open, jump straight to the next start, so the loop runs O(n) times.

Java

public int maxEvents(int[][] events) {
    Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));
    PriorityQueue<Integer> ends = new PriorityQueue<>(); // deadlines of open events
    int n = events.length, i = 0, day = 0, attended = 0;
    while (i < n || !ends.isEmpty()) {
        if (ends.isEmpty()) day = events[i][0]; // skip idle days
        while (i < n && events[i][0] <= day) {
            ends.offer(events[i][1]);
            i++;
        }
        while (!ends.isEmpty() && ends.peek() < day) ends.poll(); // missed
        if (!ends.isEmpty()) {
            ends.poll(); // attend the one expiring soonest
            attended++;
        }
        day++;
    }
    return attended;
}

Each event enters and leaves the heap once — fast and independent of D.

Pro tip

The Better approach becomes near-linear if a union-find maps each day to its next free day — a nice alternative to mention.

At a glance

Level	Approach	Time	Space
Brute Force	Backtracking over Day Assignments	`O((D+1)ⁿ)`	`O(n + D)`
Better	Earliest Deadline First + Day Scan	`O(n log n + n·D)`	`O(D)`
Optimal	Day Sweep with Min-Heap of End Days	`O(n log n)`	`O(n)`

Common pitfalls

Sorting by start and attending greedily — a long early event steals a short one's day.
Forgetting to drop expired end days before polling the heap.
Looping over every day up to 10⁵ even when no event is open (fine, but jump).

Interview tips

Name the rule: earliest deadline first, and sketch the exchange argument.
Clarify that an event needs just one day, not its whole range.
Contrast with Non-overlapping Intervals, where an event occupies its whole span.

Pattern

Sweep + min-heap of deadlines → schedule unit-length jobs inside time windows to maximise count.

My notes saved in this browser