🌱 Keegan's Digital Garden

1353. Maximum Number of Events That Can Be Attended

2 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- each event has a start day and an end day 
- you can only attend one event per day 
- an event can be attended on any day within its range

🤔What Did I Struggle With?

- question description doesnt do a good job of explaining that days can technically 'overlap'

💡 Explanation of Solution

Greedy approach : choose the earliest ending event available on each day
Use a priority queue (min heap) to choose the earliest ending day

1. find max end day
2. sort events by start day
3. use min heap (priority queue) to track active events
4. iterate day by day from 1 to maxDays, maintain active events
5. return res

⌛ Complexity Analysis

Time Complexity: O(n log n)
- sorting associated with the insertion operation of the priority queue 
- initial sort of the list by start date

Space Complexity: O(n)
- storage of elements in priority queue

💻 Implementation of Solution

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        int res = 0;
        int maxEndDay = 0;
 
        // Step 1: Find the maximum end day among all events
        for (auto& event : events)
            maxEndDay = max(maxEndDay, event[1]);
 
        // Step 2: Sort events by start day (greedy strategy)
        sort(events.begin(), events.end());
 
        // Step 3: Track active events using a min-heap (priority queue)
        int j = 0;  // Pointer to track events in the sorted array
        priority_queue<int, vector<int>, greater<int>> pq;  // Min-heap to store event end days
 
        // Step 4: Process each day from 1 to maxEndDay
        for (int day = 1; day <= maxEndDay; day++) {
            // 1. Remove events that have expired before today
            while (!pq.empty() && pq.top() < day) {
                pq.pop();
            }
 
            // 2. Add all events that start today to the heap (sorted by end day)
            while (j < events.size() && events[j][0] == day) {
                pq.push(events[j][1]);  // Store only the end day
                j++;  // Move to the next event
            }
 
            // 3. Attend the event that ends the earliest (smallest end day)
            if (!pq.empty()) {
                pq.pop();  // Remove the attended event
                res++;  // Increment count of attended events
            }
        }
 
        return res;
    }
};

Graph View