[Leetcode] 1353. Maximum Number of Events That Can Be Attended

https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/?envType=daily-question&envId=2025-07-07

initial

i just thought sorting via start and end date would work.

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        time=1
        ans=0
        events.sort(key = lambda x:(x[0],x[1]))
        for event in events:
            start,end = event
            if start<=time<=end:
                ans+=1
            time+=1
        return ans

but if [[1,4],[4,4],[2,2],[3,4],[1,1]], it doesnt work. So i thought for a while and idea of using heap like the balloon interval question popped up. But I missed core logic cuz I thought of putting both start and end date as tuple and if len(heap) is less than the current end date, we can append this particular event. But its still wrong for that edge case

import heapq
class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        time=1
        ans=0
        events.sort(key = lambda x:x[0])
        print(events)
        # for event in events:
        #     start,end = event
        #     if start<=time<=end:
        #         ans+=1
        #     time+=1
        # return ans
        heap=[]
        heapq.heapify(heap)
        for event in events:
            start,end=event
            if not heap or len(heap)<=end or heap[0][1]>end:
                ans+=1
                heapq.heappush(heap,(start,end))
            else:
                heapq.heappop(heap)
        return len(heap)

        # 1,100
        # 3,5
        # 1,10

sol

the core logic is we wanna store the end date in our heap. And looking at that edge case, when you have multiple events you could attend on the same day, you should attend the one that ends earliest.

We should also pop the inactive end dates as we iterate through day by day cuz why?

Events: [[1,2], [3,4]]
Day 1: Event [1,2] starts → heap = [2]
Day 2: You skip this day (don't attend anything) → heap = [2]
Day 3: Event [3,4] starts → heap = [2, 4]

Day 4 - Without cleanup:

heap = [2, 4]
You pop 2 and think "I'll attend the event ending on day 2"
But that's impossible! You're on day 4, and that event ended on day 2 so u need to clean up this day 2!

Day 4 - With cleanup:

First, remove expired events: 2 < 4, so remove 2 → heap = [4]
Now pop 4 → correctly attend the event ending on day 4

another example this edge case
[1,4],[4,4],[2,2],[3,4],[1,1]]
Day 1:

Events [1,1] and [1,4] start → heap = [1, 4] (min heap)
Pop earliest ending: pop 1 → ans = 1
heap = [4]

Day 2:

Event [2,2] starts → heap = [4, 2] → min heap = [2, 4]
Pop earliest ending: pop 2 → ans = 2
heap = [4]

Day 3:

Event [3,4] starts → heap = [4, 4]
Pop earliest ending: pop 4 → ans = 3
heap = [4]

Day 4:

Event [4,4] starts → heap = [4, 4]
Pop earliest ending: pop 4 → ans = 4
heap = [4]

import heapq
class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        time=1
        ans=0
        events.sort(key = lambda x:(x[0],x[1]))
        heap=[]
        heapq.heapify(heap)
        for cur_day in range(1,10**5 +1):
            while events and events[0][0]==cur_day:
                heapq.heappush(heap, events[0][1])
                events.pop(0)
            while heap:
                if heap[0]<cur_day:
                    heapq.heappop(heap)
                else:
                    break
            if heap:
                heapq.heappop(heap)
                ans+=1
        return ans

complexity

n log n time cuz of sort
n events worst