Maximum Number of Events That Can Be Attended
Understanding the Problem
Each event spans a range of days, and you pick one day within that range to attend it. You can only attend one event per day. The goal is to maximize how many events you attend in total.
The decision is which day to assign to which event. Attending events on their start day fails: it can block a shorter event that has no other day available. If event A spans days 1-3 and event B only spans day 1, attending A on day 1 wastes B's only chance. Attending B on day 1 and A on day 2 saves both.
This is a scheduling problem. When multiple events are available on a given day, attend the one that ends soonest. An event ending sooner has fewer remaining days on which it could be attended, so delaying it risks losing it entirely. Events with later end days have more slack and can wait.
Key Constraints:
1 <= events.length <= 10^5→ With up to 100,000 events, an O(n^2) approach reaches 10^10 operations and times out. The target is O(n log n) or better.1 <= startDayi <= endDayi <= 10^5→ Days go up to 100,000. Iterating once over all days is feasible (10^5 iterations), but iterating over every day-event pair is not.events[i].length == 2→ Each event is a start-end pair with no weights, so this is an unweighted maximum-matching problem rather than a weighted one.
Approach 1: Brute Force (Greedy with Set)
Intuition
Sort the events by end day so the ones with the earliest deadline come first, then for each event attend it on the earliest available day within its range. A set tracks which days are already taken.
Processing events by end day first protects the urgent ones. An event ending sooner has fewer candidate days, so committing those events before the flexible ones keeps a later-ending event from stealing a day that an earlier-ending event still needs.
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 log n + n d). Sorting costs O(n log n). For each of the n events, the inner loop scans up to d days (d is the maximum span, up to 10^5), and the O(n log n) sort is dominated by the O(n d) scanning term, which can reach 10^10.
- Space Complexity: O(n). The usedDays set holds at most n entries, one per attended event.
This is correct but too slow when events span many days, since the inner day scan dominates. The next approach removes that scan by processing one day at a time and using a min-heap to pick the best available event in O(log n).
Approach 2: Greedy with Sorting + Min-Heap
Intuition
Instead of iterating event-by-event, iterate day-by-day. On each day, consider all events that are currently active (started but not yet ended) and attend the one with the earliest end day. That event has the fewest remaining days, so skipping it today risks losing it when it expires, while events ending later still have days to spare.
The min-heap makes "earliest end day among active events" cheap to query. Sort events by start day so they become active in order. Walk through the days from 1 to the maximum end day. On each day, push every event starting that day into a min-heap keyed by end day, discard any events already past their end day, then pop the event with the smallest end day and attend it.
An exchange argument shows the earliest-end-day choice is optimal. Suppose an optimal solution attends event X on day d while event Y, which ends no later than X and is also active on day d, goes unattended. Swap them: attend Y on day d, and move X to any free day in its range. Such a day exists because X ends no earlier than Y, so X's range covers at least the days Y's did, minus day d. The swap keeps the attended count the same and brings the solution one step closer to the greedy choice. Repeating it transforms any optimal solution into the greedy one without reducing the count.
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.