DSA problem
Maximum Number of Events That Can Be Attended
You are given an array of events where events[i] = [startDay_i, endDay_i]. Each event i starts at startDay_i and ends at endDay_i. You can attend an event on any single day d with startDay_i <= d <= endDay_i, but you can attend only one event per day. Return the maximum number of events you can attend.
The greedy intuition is delicate. If you could attend more than one event per day, the problem would be trivial. The constraint that each day can host only one event turns this into a scheduling problem where, on each day, you should attend the event that is most about to expire — the one whose endDay is smallest among events currently in progress.
This greedy choice is optimal because postponing an event with end day e is risky: tomorrow it might have expired entirely. Meanwhile, an event with a later end day can wait one more day. Therefore on every day you should commit to the most urgent currently-available event.
The standard implementation iterates day by day from 1 to the maximum end day, using a min-heap keyed on end day to find the most urgent active event. At each day, push the end days of every event that starts today, pop and discard expired events whose end day is in the past, and if the heap is non-empty pop one event and count it. The algorithm runs in O((D + n) log n) time where D is the maximum end day; the constraints make this practical (n, D up to ~10^5).
Examples
events = [[1,2],[2,3],[3,4]]3events = [[1,2],[2,3],[3,4],[1,2]]4events = [[1,4],[4,4],[2,2],[3,4],[1,1]]4Constraints
- 1 <= events.length <= 10^5
- events[i].length == 2
- 1 <= startDay_i <= endDay_i <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.