Maximum Number of Events That Can Be Attended: Greedy Heap Pattern

You are given a list of events where events[i] = [startDay, endDay]. Each event can be attended on any single day within its range (inclusive). You can attend at most one event per day. Return the maximum number of events you can attend.

This is LeetCode 1353: Maximum Number of Events That Can Be Attended, a medium problem that combines greedy thinking with a min-heap. The trick is figuring out which event to attend each day, and the answer is always the same: pick the one that ends the soonest.

Why this problem matters

This problem is a gateway to the "greedy scheduling with a heap" pattern. The same idea shows up in meeting room allocation, task scheduling, and job sequencing problems. Once you internalize the rule of "always pick the most urgent item from the available set," you can apply it across dozens of similar problems.

The challenge is not brute force. It is recognizing that a min-heap lets you efficiently track which events are still available and which one has the earliest deadline.

The brute force trap

A naive approach would try every possible assignment of days to events. But with up to 10^5 events and 10^5 possible days, this blows up quickly. Even a simulation that scans all events for each day would be O(days * events), which is too slow.

The key observation is that you do not need to consider all events on every day. You only need to consider events that have started but not yet expired. A min-heap gives you the one with the earliest deadline in O(log n) time.

The approach: sort, sweep, and heap

Here is the strategy:

1. Sort the events by start day.
2. Iterate through days from the earliest start to the latest.
3. On each day, push the end days of all events that start on this day into a min-heap.
4. Remove any events from the heap whose end day has already passed (they expired).
5. Pop the smallest end day from the heap. That is the event you attend today, because it is the most urgent.
6. Increment your count.

If the heap is empty on a given day, skip ahead to the next event's start day. This avoids wasting time on empty days.

The greedy solution

import heapq

def max_events(events: list[list[int]]) -> int:
    events.sort()
    heap = []
    i = 0
    count = 0
    n = len(events)
    day = events[0][0]

    while i < n or heap:
        if not heap:
            day = events[i][0]
        while i < n and events[i][0] == day:
            heapq.heappush(heap, events[i][1])
            i += 1
        heapq.heappop(heap)
        count += 1
        day += 1
        while heap and heap[0] < day:
            heapq.heappop(heap)

    return count

Let's break this down piece by piece.

Sorting: events.sort() sorts by start day first, then by end day. This lets us process events in chronological order with a simple index scan.

The main loop: We continue as long as there are unprocessed events (i < n) or events still in the heap. Each iteration handles one day.

Skipping empty days: If the heap is empty but events remain, we jump day forward to the next event's start day. No point iterating through days where nothing is available.

Pushing new events: All events that start on the current day get their end days pushed into the min-heap. The heap now contains the deadlines of every event we could attend today.

Attending an event: We pop the smallest end day. That is the event closest to expiring, so we attend it. Increment count.

Cleaning up expired events: After moving to the next day, we remove any events from the heap whose end day is now in the past. They can no longer be attended.

Walking through it step by step

Let's trace the algorithm on events = [[1,2],[2,3],[3,4],[1,3]].

After sorting by start day, the order becomes [[1,2],[1,3],[2,3],[3,4]].

The algorithm processes 4 days and attends one event per day. Every event gets attended because we always chose the one ending soonest, leaving room for later events on future days.

Complexity analysis

Sorting takes O(n log n). Each event is pushed and popped from the heap at most once, and each heap operation is O(log n). The total work across all days is O(n log n). Space is O(n) for the heap in the worst case where all events overlap.

Building blocks

This problem is built on two reusable patterns.

1. Greedy deadline scheduling

The core idea is that when you have multiple tasks with deadlines, always do the most urgent one first:

while heap:
    deadline = heapq.heappop(heap)
    if deadline >= current_day:
        count += 1
        current_day += 1

This pattern shows up whenever you need to maximize the number of tasks completed before their deadlines. The min-heap ensures you always know which task is most urgent.

2. Sweep line with lazy addition

Instead of checking all events on every day, you sweep through days and add events to the active set only when their start day arrives:

while i < n and events[i][0] == day:
    heapq.heappush(heap, events[i][1])
    i += 1

This "lazy addition" pattern is common in interval problems. You sort by one endpoint, then process the other endpoint with a data structure. The same idea powers the sweep line in Meeting Rooms II and the merge step in Merge Intervals.

Edge cases

Before submitting, make sure your solution handles these:

• Single event [[1,1]]: one event, one day. Return 1.
• All events on the same day [[1,1],[1,1],[1,1]]: only one event can be attended per day. Return 1.
• No overlaps [[1,1],[2,2],[3,3]]: each event gets its own day. Return 3.
• Large gaps between events [[1,1],[100000,100000]]: the "skip ahead" logic (day = events[i][0]) handles this efficiently without iterating through 99,998 empty days.
• Events that have already expired when we reach them: the cleanup loop while heap and heap[0] < day handles this by discarding them.

The greedy solution handles all of these without any special-case logic.

From understanding to recall

You have read the greedy-heap solution and it makes sense. Sort by start, push end days, pop the smallest, clean up expired ones. But can you write it from scratch in an interview without looking at notes?

The details matter: initializing day to the first event's start, using heappop to attend the most urgent event, and cleaning up the heap after incrementing the day. These are small decisions that are easy to fumble under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the greedy-heap loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "maximize events attended with deadlines" and the code flows out without hesitation.

The greedy-heap scheduling pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Meeting Rooms II - Uses a min-heap to track overlapping intervals and find the peak number of concurrent meetings
• Task Scheduler - Another greedy scheduling problem where frequency counting replaces the heap
• Merge Intervals - The foundational interval sorting pattern that this problem builds on

CodeBricks breaks the maximum events attended problem into its greedy-heap and sweep-line building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a scheduling problem shows up in your interview, you do not think about it. You just write it.