Maximum Number of Events That Can Be Attended
Medium · Intervals · Array · Greedy · Sorting · Heap (Priority Queue)
Problem
You are given events, where events[i] = [start_i, end_i]. You may attend event i on any one day d with start_i <= d <= end_i. Attending takes the whole day, so you can attend at most one event per day.
Return the largest number of events you can attend.
Examples
Input: events = [[1,1],[1,2],[1,2],[3,3]] Output: 3
Attend one event on each of days 1, 2 and 3; the fourth has no free day left.
Input: events = [[2,4],[2,4],[2,4]] Output: 3
Days 2, 3 and 4, one per event.
Input: events = [[5,5],[5,5]] Output: 1
Both need day 5, so only one fits.
Constraints
- 1 <= len(events) <= 10^5
- events[i].length == 2
- 1 <= start_i <= end_i <= 10^5
Approaches
- Baseline: soonest end first, earliest free day — time O(n · D), space O(D)
Follow-up
What if you can attend up to c events per day? The same sweep pops up to c events each day: the first use case below. And when events carry values and last several days, the greedy no longer works; that version needs dynamic programming over events sorted by end.
Related problems
Start free on Cariara · Coding problems · System design studio
