1353.Maximum_Number_of_Events_That_Can_Be_Attended(Medium).md

1353. Maximum Number of Events That Can Be Attended (Medium)

Link: https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended

Date	Stopwatch	Y/N	Feedback
Jul 10, 2025	27m	Y

Edge Cases:

Edge Case:

Input: eventws = [[1,2],[1,2],[3,3],[1,5],[1,5]]
Output: 5

Walk-through:

1. For interval type question, it is a good habit to sort first.

2. Find the max_end_day from events, so we can loop over day i in [1, max_end_day]. For each day i, we are adding start_day < i from events, and we heappush() event[j]'s end_day into minHeap, otherwise, the start_day won't help us to keep the correct order in minHeap (edge case).

3. Check minHeap's end_day from the top of minHeap, if minHeap[0] < i, we need to remove this event from minHeap, because we will not be able to take this event after day i.

4. Lastly, if minHeap is not empty, we take this current event in the top of minHeap and increment ans += 1.

Python:

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        # 1. Sort events and find max end day from events
        # 2. Loop over each day i [0, max_day+1], and add days into minHeap if start <= i, also exclude end_day in minHeap < i
        # TC: O(nlog(n) + nlog(k)), n=len(events), k=len(minHeap), SC: O(k)
        
        events = sorted(events)
        j = 0   # event index
        ans = 0
        minHeap = []
        max_day = max(event[1] for event in events)
        # Loop over each day i
        for i in range(1, max_day + 1):
            # Add start_day < i into minHeap
            while j < len(events) and events[j][0] <= i:
                # Only add the end_day into minHeap, otherwise we can't keep the correct order in minHeap
                heapq.heappush(minHeap, events[j][1])
                j += 1
            # Remove previous end_day < i from minHeap
            while minHeap and minHeap[0] < i:
                heapq.heappop(minHeap)
            # Increment ans assume we attend the meeting in the top of minHeap
            if minHeap:
                ans += 1
                heapq.heappop(minHeap)
        return ans

Time Complexity: $O(nlog(n+k))$, n=len(events), k=len(minHeap), O(nlog(n)) for sorting events, O(nlog(k)) for heap operation on each day.
Space Complexity: $O(k)$