<p>You are given an array of <code>events</code> where <code>events[i] = [startDay<sub>i</sub>, endDay<sub>i</sub>]</code>. Every event <code>i</code> starts at <code>startDay<sub>i</sub></code><sub> </sub>and ends at <code>endDay<sub>i</sub></code>.</p>

<p>You can attend an event <code>i</code> at any day <code>d</code> where <code>startTime<sub>i</sub> &lt;= d &lt;= endTime<sub>i</sub></code>. You can only attend one event at any time <code>d</code>.</p>

<p>Return <em>the maximum number of events you can attend</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/02/05/e1.png" style="width: 400px; height: 267px;" />
<pre>
<strong>Input:</strong> events = [[1,2],[2,3],[3,4]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> events= [[1,2],[2,3],[3,4],[1,2]]
<strong>Output:</strong> 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= events.length &lt;= 10<sup>5</sup></code></li>
	<li><code>events[i].length == 2</code></li>
	<li><code>1 &lt;= startDay<sub>i</sub> &lt;= endDay<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        if events is None:
            return 0
        
        min_heap = []
        start = float("inf")
        end = float("-inf")

        for event in events:
            heapq.heappush(min_heap, event[1])
            start = min(start, event[0])
            end = max(end, event[1])
        
        ans = 0
        cur = start
        events.sort()
        could_attend = []
        while cur <= end:
            while events:
                tmp_start, tmp_end = events[0][0], events[0][1]
                if tmp_start <= cur:
                    heapq.heappush(could_attend, tmp_end)
                    events.pop(0)
                else:
                    break
                
            while could_attend:
                tmp = heapq.heappop(could_attend)
                if tmp < cur:
                    continue
                else:
                    ans += 1
                    break
            cur += 1
        return ans
















#5/17/2024
# greedy + heap
# class Solution:
#     def maxEvents(self, events: List[List[int]]) -> int:
#         if events is None:
#             return 0
        
#         start, end = min([each[0] for each in events]), max([each[1] for each in events])
#         min_heap = []
#         events.sort()
#         could_attend = []
#         ans = 0
#         cur = start

#         while cur <= end:
#             print("first")
#             while events:
#                 tmp_start, tmp_end = events[0]
#                 if tmp_start <= cur:
#                     print("here")
#                     heapq.heappush(could_attend, events[0][1])
#                     events.pop(0)
#                 else:
#                     break
#             while could_attend:
#                 tmp = heapq.heappop(could_attend)
#                 print("tmp: ", tmp)
#                 if tmp < cur:
#                     continue
#                 else:
#                     ans += 1
#                     break
#             cur += 1
#         return ans





















# 2/20/2024
# greedy
# class Solution:
#     def maxEvents(self, events: List[List[int]]) -> int:
#         if events is None:
#             return 0
        
#         ans = 0
#         cur = min([event[0] for event in events])
#         max_val = max([event[1] for event in events])
#         could_attend = []
#         events.sort()
#         heap = []

#         while cur <= max_val:
#             while events:
#                 start, end = events[0]
#                 if start <= cur:
#                     heapq.heappush(could_attend, end)
#                     events.pop(0)
#                 else:
#                     break
#             while could_attend:
#                 tmp_end = could_attend[0]
#                 if tmp_end < cur:
#                     heapq.heappop(could_attend)
#                     continue
#                 else:
#                     ans += 1
#                     heapq.heappop(could_attend)
#                     break
#             cur += 1
        
#         return ans

























# 12/22/2023
# greedy + heap
# class Solution:
#     def maxEvents(self, events: List[List[int]]) -> int:
#         # for each day, which event started already and ends first, attend that;
#         if events is None:
#             return 0

#         n = len(events)
#         min_heap = []

#         tmp = []
#         start, last = float("inf"), float("-inf")

#         for event in events:
#             start = min(start, event[0])
#             last = max(last, event[1])
#         cur = start
#         events.sort()
#         ans = 0

#         while cur <= last:
#             while events:
#                 first = events[0]
#                 if first[0] <= cur and first[0] >= cur:
#                     heapq.heappush(min_heap, events.pop(0)[1])
#                 else:
#                     break
            
#             while min_heap:
#                 if min_heap[0] < cur:
#                     heapq.heappop(min_heap)
#                 else:
#                     break
            
#             if len(min_heap) > 0:
#                 heapq.heappop(min_heap)
#                 ans += 1
#             cur += 1
        
#         return ans
            




        


































# 9/29/2023
# min heap + greedy
# class Solution:
#     def maxEvents(self, events: List[List[int]]) -> int:
#         # [1, 5], [1, 2], [1, 4], [3, 3], [1, 1]
#         # [1, 1], [1, 2], [1, 4], [1, 5], [3, 3] 0
#         # [1, 5], [1, 4], [3, 3], [1, 2], [1, 1] 1
#         if events is None:
#             return 0
#         heap = []
#         events.sort()
#         cur = events[0][0]
#         ans = 0
#         end = 0
#         for each in events:
#             end = max(end, each[1])
#         print("cur, end: ", cur, end)

#         while cur <= end:
#             while events:
#                 tmp = events[0] 
#                 if tmp[0] > cur:
#                     break
#                 heapq.heappush(heap, tmp[1])
#                 events.pop(0)
            
#             while heap:
#                 first = heapq.heappop(heap)
#                 if first < cur:
#                     continue
#                 ans += 1
#                 break
#             cur += 1
        
#         return ans
        






















# 5/30/2023
# greedy
# class Solution:
#     def maxEvents(self, events: List[List[int]]) -> int:
#         if events is None:
#             return 0

#         heap = []
#         ans = 0

#         start, end = float("inf"), float("-inf")

#         for event in events:
#             start = min(event[0], start)
#             end = max(event[1], end)

#         cur = start
#         events.sort()
#         while cur <= end:
#             while events:
#                 if events[0][0] <= cur:
#                     heapq.heappush(heap, events[0][1])
#                     events.pop(0)
#                 else:
#                     break
#             while heap:
#                 tmp = heapq.heappop(heap)
#                 if tmp >= cur:
#                     ans += 1
#                     break
#                 else:
#                     continue
#             cur += 1
        
#         return ans


























# 3/6/2023
# greedy + heap
# class Solution:
#     def maxEvents(self, events: List[List[int]]) -> int:
#         if events is None:
#             return 0
        
#         n = len(events)
#         heap = []
#         cur = 1

#         ans = 0
#         max_day = max([each[1] for each in events])
#         events.sort()

#         while cur <= max_day:
#             while events:
#                 if events[0][0] <= cur:
#                     heapq.heappush(heap, events[0][1])
#                 else:
#                     break
#                 events.pop(0)
            
#             while heap:
#                 tmp = heapq.heappop(heap)
#                 if tmp < cur:
#                     continue
#                 else:
#                     ans += 1
#                     break
#             cur += 1

#         return ans
                
























# 12/25/2022
# greedy + min_heap
# class Solution:
#     def maxEvents(self, events: List[List[int]]) -> int:
#         if events is None:
#             return 0
        
#         n = len(events)

#         min_heap = []
#         events.sort()
#         max_day = max([event[1] for event in events])
        
#         today = 1
#         ans = 0
#         while today <= max_day:
#             while events:
#                 if events[0][0] <= today:
#                     heapq.heappush(min_heap, events.pop(0)[1])
#                 else:
#                     break
            
#             while min_heap:
#                 if min_heap[0] < today:
#                     heapq.heappop(min_heap)
#                 else:
#                     break
            
#             if len(min_heap) > 0:
#                 heapq.heappop(min_heap)
#                 ans += 1
#             today += 1


        
#         return ans
        

        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
# 10/13/2022
# min heap + greedy
# class Solution:
#     def maxEvents(self, events: List[List[int]]) -> int:
#         if events is None:
#             return 0
        
#         n = len(events)
        
#         min_heap = []
#         today = 1
#         events.sort()
#         max_end_date = max([each[1] for each in events])
#         ans = 0
        
#         for i in range(1, max_end_date + 1):
#             while len(events) > 0:
#                 if events[0][0] <= today:
#                     heapq.heappush(min_heap, events.pop(0)[1])
#                 else:
#                     break
            
#             while len(min_heap) > 0:
#                 if min_heap[0] < today:
#                     heapq.heappop(min_heap)
#                 else:
#                     break
            
#             if len(min_heap) > 0:
#                 heapq.heappop(min_heap)
#                 ans += 1
#             today += 1
        
#         return ans
                    
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
# 9/5/2022
# min_heap + greedy
# class Solution:
#     def maxEvents(self, events: List[List[int]]) -> int:
#         if events is None:
#             return 0
        
#         n = len(events)
#         events.sort()
        
#         min_heap = []
#         day = events[0][0]
#         max_day = max([each[1] for each in events])
#         ans = 0
#         event_index = 0
#         n = len(events)
        
#         while day <= max_day:
#             while event_index < n and events[event_index][0] <= day:
#                 heapq.heappush(min_heap, events[event_index][1])
#                 event_index += 1
            
#             while min_heap and min_heap[0] < day:
#                 heapq.heappop(min_heap)
            
#             if min_heap:
#                 ans += 1
#                 heapq.heappop(min_heap)
            
#             day += 1
                
#         return ans
            
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
# 7/4/2022
# greedy
# class Solution:
#     def maxEvents(self, events: List[List[int]]) -> int:
#         if events is None:
#             return 0
        
#         event_index, ans, day = 0, 0, 1
#         events.sort()
#         min_heap = []
#         n = len(events)
#         max_day = max([each[1] for each in events])
        
#         while day <= max_day:
            
#             while event_index < n and events[event_index][0] <= day:
#                 heapq.heappush(min_heap, events[event_index][1])
#                 event_index += 1
            
#             while len(min_heap) > 0 and min_heap[0] < day:
#                 heapq.heappop(min_heap)
            
#             if min_heap:
#                 ans += 1
#                 heapq.heappop(min_heap)
            
#             day += 1
        
#         return ans
            
                
                
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
# 6/6/2022
# greedy + min-heap
# class Solution:
#     def maxEvents(self, events: List[List[int]]) -> int:
#         if events is None:
#             return 0
        
#         n = len(events)
#         event_index, day, ans = 0, 1, 0
#         events.sort()
#         max_day = max([events[i][1] for i in range(n)])
#         min_heap = []
        
#         while day <= max_day:
            
#             while event_index < n and events[event_index][0] <= day:
#                 heapq.heappush(min_heap, events[event_index][1])
#                 event_index += 1
            
#             while min_heap and min_heap[0] < day:
#                 heapq.heappop(min_heap)
            
#             if min_heap:
#                 ans += 1
#                 heapq.heappop(min_heap)
            
#             day += 1
        
#         return ans
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        

# 4/20/2022
# min-heap + greedy
# class Solution:
#     def maxEvents(self, events: List[List[int]]) -> int:
#         if events is None:
#             return 0
        
#         n = len(events)
#         events = sorted(events)
#         max_day = max([events[i][1] for i in range(n)])
#         min_heap = []
#         day, ans, event_index = 1, 0, 0
#         while day <= max_day:
            
#             while event_index < n and events[event_index][0] <= day:
#                 heapq.heappush(min_heap, events[event_index][1])
#                 event_index += 1
            
#             while min_heap and min_heap[0] < day:
#                 heapq.heappop(min_heap)
#             if min_heap:
#                 heapq.heappop(min_heap)
#                 ans += 1
            
#             day += 1
#         return ans
            
52800