Maximum Number of Events That Can Be Attended
Last Updated: April 4, 2026
Understanding the Problem
Think of this like scheduling meetings on a calendar. Each event spans a range of days, and you need to pick exactly one day to attend each event. The catch: you can only attend one event per day. The goal is to maximize how many events you attend in total.
The tricky part is choosing which day to assign to which event. If you greedily attend events on their start day, you might block a shorter event that could only be attended that day. For example, if event A spans days 1-3 and event B only spans day 1, attending A on day 1 wastes B's only chance. You should attend B on day 1 and A on day 2 instead.
This is fundamentally a scheduling problem. The key observation is: when multiple events are available on a given day, you should attend the one that ends soonest. An event ending sooner has fewer future days where it could be attended, so delaying it is riskier. Events with later end days have more flexibility and can wait.
Key Constraints:
1 <= events.length <= 10^5→ With up to 100,000 events, O(n^2) is borderline (10^10 in the worst case). We need O(n log n) or better.1 <= startDayi <= endDayi <= 10^5→ Days go up to 100,000. Iterating over all days is feasible, but iterating over all day-event pairs is not.events[i].length == 2→ Each event is just a start-end pair. No weights or priorities.
Approach 1: Brute Force (Greedy with Set)
Intuition
The most straightforward idea: sort the events by end day (so shorter-deadline events come first), then for each event, try to attend it on the earliest available day within its range. We use a set to track which days are already taken.
This greedy choice makes sense because events ending sooner have fewer options. By handling them first, we avoid accidentally blocking them.
Algorithm
- Sort events by end day. If end days are equal, sort by start day.
- Create a set
usedDaysto track days that are already assigned. - For each event
[start, end], iterate fromstarttoendlooking for an unused day. - If an unused day is found, mark it as used and increment the count.
- Return the total count.
Example Walkthrough
Code
- Time Complexity: O(n d). We sort in O(n log n). For each of the n events, we might scan up to d days (where d is the max span, up to 10^5). In the worst case this is O(n d), which can reach 10^10.
- Space Complexity: O(n). The usedDays set can hold up to n entries.
This approach works correctly but is too slow for large inputs where events span many days. What if we processed events day-by-day instead of event-by-event, using a priority queue to pick the best event in O(log n)?
Approach 2: Greedy with Sorting + Min-Heap
Intuition
Instead of iterating event-by-event, flip the perspective: iterate day-by-day. On each day, look at all events that are currently active (started but not yet ended), and attend the one with the earliest end day. Why the earliest end day? Because that event has the fewest remaining days to be attended. If we skip it today, it might expire tomorrow. Events ending later can afford to wait.
Here's how it works: sort events by start day. Walk through the days from 1 to max. On each day, push all events starting that day into a min-heap (keyed by end day). Remove any events from the heap that have already expired. Then pop the event with the smallest end day and attend it.
This greedy strategy works because of an exchange argument. Suppose the optimal solution attends event X on day d, but event Y (ending sooner than X) is also available on day d and isn't attended at all. We could swap: attend Y on day d instead and attend X on some later day (X has a later end day, so it has more available days). This swap never decreases the total count. So the greedy choice of always attending the earliest-ending event is optimal.
Algorithm
- Sort events by start day.
- Find the maximum end day across all events (this determines our day range).
- Use a pointer
ito track which events we've added to the heap. - For each day from 1 to maxDay:
- Add all events starting on this day to a min-heap (keyed by end day).
- Remove expired events from the top of the heap (events where endDay < current day).
- If the heap is non-empty, pop the event with the smallest end day and increment the count.
- Return the count.
Example Walkthrough
Code
- Time Complexity: O(d + n log n). Sorting takes O(n log n). We iterate over d days (up to 10^5). Each event is pushed and popped from the heap at most once, costing O(log n) per operation. Total heap operations: O(n log n). The overall cost is O(d + n log n).
- Space Complexity: O(n). The heap holds at most n events at any time.