Maximum Number of Events That Can Be Attended - Solution & Explanation

Problem Overview: You are given an array where events[i] = [startDay, endDay]. Each event can be attended on any single day within its range. The goal is to attend the maximum number of events without attending more than one event per day.

Approach 1: Greedy with Sorting and Set (Time: O(n log n + D log D), Space: O(D))

This approach uses a greedy scheduling idea. First sort the events by their ending day so that events that expire earlier are considered first. Maintain a sorted set of available days (typically from 1 to maxDay). For each event, use a set operation such as lower_bound to find the earliest available day that is greater than or equal to its start day. If that day is within the event's end day, attend the event and remove the day from the set.

The key insight is simple: always occupy the earliest valid day for an event so later days remain available for other events. Sorting ensures events that expire sooner get priority. This method relies heavily on ordered set operations and works well when the day range is manageable.

Approach 2: Priority Queue (Min-Heap) Method (Time: O(n log n), Space: O(n))

This is the most common and scalable solution. Start by sorting events by their start day. Iterate through days in increasing order and maintain a min-heap that stores the end days of events that have already started but not yet been attended. When the current day reaches an event's start day, push its end day into the heap.

At each day, remove events from the heap whose end day is earlier than the current day because they are already expired. Then attend the event with the smallest end day by popping the heap. Choosing the event that ends earliest prevents losing opportunities for short intervals. Each event is inserted and removed from the heap at most once, giving an efficient O(n log n) runtime.

This approach combines greedy scheduling with a heap (priority queue) while relying on initial sorting. It handles large day ranges efficiently because it only processes relevant events rather than tracking every possible day explicitly.

Recommended for interviews: The priority queue solution is what most interviewers expect. It demonstrates understanding of greedy scheduling and efficient event selection using a min-heap. Mentioning the set-based greedy idea shows good intuition, but implementing the heap approach proves you can manage dynamic candidate events efficiently with O(n log n) complexity.