Maximum Number of Events That Can Be Attended
Asked at Snowflake
Problem
Maximum Number of Events That Can Be Attended gives you events with a start day and end day; you can attend an event on any single day within its range, and at most one event per day. How many events can you attend? The greedy rule: each day, attend the available event that ends soonest.
Asked At
| Company | Difficulty | |
|---|---|---|
| Snowflake | Medium | View all Snowflake questions → |
How to Think About It
Sorting by end day and assigning each event its earliest free day works but needs a structure to find free days quickly.
Key insight: sweep day by day. On each day, all events that have started are candidates. Attend the one with the earliest end day — it has the least flexibility, and any other choice can be exchanged for it without losing events.
Implementation: sort events by start day. Keep a min-heap of end days of events that have started. Each day: push newly started events, pop events that already ended, then attend one (pop the top) if any remain.
Jump the current day forward to the next event's start when the heap is empty, so you do not iterate over long idle stretches.
Walkthrough: [[1,2],[2,3],[3,4],[1,2]]: day 1 attend an end-2 event; day 2 attend the other end-2 event; day 3 attend [2,3]; day 4 attend [3,4] -> 4.
Optimal Approach
Step 1: Sort events by start day.
Step 2: heap = [], i = 0, day = 0, res = 0.
Step 3: While i < n or heap:
If heap is empty, set day = events[i].start.
Push the end day of every event with start <= day.
Pop ends < day (expired).
If heap is not empty: pop one, res += 1.
day += 1.
Step 4: Return res.
Time: O(n log n). Space: O(n).
What Trips People Up in Real Interviews
Greedily picking events by earliest start. An early-starting event with a far end day can wait.
Iterating over every day up to 10^5 without skipping idle stretches — fine here, but jumping ahead is cleaner.
Forgetting to discard expired events before attending one.
Treating it like interval scheduling (non-overlapping intervals). Here you only need one day inside each event, not the whole interval.
Solution Code
import heapq
def maxEvents(events):
events.sort()
heap = []
i = res = day = 0
n = len(events)
while i < n or heap:
if not heap:
day = max(day, events[i][0])
while i < n and events[i][0] <= day:
heapq.heappush(heap, events[i][1])
i += 1
while heap and heap[0] < day:
heapq.heappop(heap)
if heap:
heapq.heappop(heap)
res += 1
day += 1
return resFrequently Asked Questions
What is the Maximum Number of Events That Can Be Attended problem?
Maximum Number of Events That Can Be Attended gives you events with a start day and end day; you can attend an event on any single day within its range, and at most one event per day. How many events can you attend? The greedy rule: each day, attend the available event that ends soonest.
How do you solve Maximum Number of Events That Can Be Attended?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximum Number of Events That Can Be Attended?
Maximum Number of Events That Can Be Attended is asked at Snowflake. It is a medium difficulty problem.
What are common mistakes on Maximum Number of Events That Can Be Attended?
- Greedily picking events by earliest start. An early-starting event with a far end day can wait.
- Iterating over every day up to `10^5` without skipping idle stretches — fine here, but jumping ahead is cleaner.
- Forgetting to discard expired events before attending one.
- Treating it like interval scheduling (non-overlapping intervals). Here you only need one day inside each event, not the whole interval.