Maximum Number of Events That Can Be Attended

Maximum Number of Events That Can Be Attended

What is this problem about?

The Maximum Number of Events That Can Be Attended coding problem gives you a list of events, each with a start day and end day. You can attend at most one event per day, and you can attend an event on any day within its [start, end] range. Maximize the number of distinct events you attend. Unlike interval scheduling where you attend the full event, here you only need one day per event.

Why is this asked in interviews?

Companies like Uber, Instacart, Microsoft, PayPal, Google, Nvidia, Amazon, and Bloomberg use this problem because it requires a non-obvious greedy with a priority queue. It tests the "earliest deadline first" insight applied to events: each day, attend the event among those currently available that ends soonest. This prevents unnecessarily blocking future events.

Algorithmic pattern used

Greedy with min-heap by end day: Sort events by start day. Use a min-heap. Iterate over days from 1 to max_end:

1. Add all events starting on or before the current day to the heap (keyed by end day).
2. Remove expired events (end day < current day) from the heap top.
3. If heap is non-empty, attend the event with the earliest end day (pop the top). Count it.

This greedy is optimal: always attending the soonest-ending available event maximizes future flexibility.

Example explanation

Events: [[1,2],[2,3],[3,4]]

• Day 1: Add [1,2]. Heap: [(2, event0)]. Attend event0. Count=1.
• Day 2: Add [2,3]. Heap: [(3, event1)]. Attend event1. Count=2.
• Day 3: Add [3,4]. Heap: [(4, event2)]. Attend event2. Count=3.
• Answer = 3.

Events: [[1,4],[4,4],[2,2],[3,4],[1,1]]

• Day 1: Add [1,4],[1,1]. Heap: [(1,e4),(4,e0)]. Attend e4 (end=1). Count=1.
• Day 2: Add [2,2]. Heap: [(2,e2),(4,e0)]. Attend e2. Count=2.
• Day 3: Add [3,4]. Heap: [(4,e0),(4,e3)]. Attend either (end=4). Count=3.
• Day 4: Add [4,4]. Attend remaining. Count=4.
• Answer = 4.

Common mistakes candidates make

• Attending events for their full duration: Each event only needs one day's attendance. Greedily pick one day per event.
• Not removing expired events: Events whose end day has passed can no longer be attended; failing to remove them leads to attending "expired" events.
• Sorting only by start without a heap: Sorting and greedily picking any valid event on each day without a heap doesn't minimize deadline, leading to suboptimal choices.

Interview preparation tip

For the Array Sorting Heap Priority Queue Greedy interview pattern, the day-by-day simulation with a min-heap is the canonical approach. The pattern: "each day, from all currently eligible items, greedily pick the one expiring soonest." This EDF (Earliest Deadline First) principle underlies dozens of scheduling problems at top tech companies. Master this template and you'll handle an entire class of greedy scheduling questions confidently.