Maximum Number of Events Attended — Greedy + Binary Search
Advertisement
Problem 325 Variant · Maximum Number of Events That Can Be Attended
Difficulty: Medium · Pattern: Greedy + Binary Search / Heap
Attend at most one event per day. Maximize count.
Solutions
# Python — sort by end day + greedy
import heapq
def maxEvents(events):
events.sort()
heap = []
n = len(events)
i = 0; day = 0; ans = 0
while heap or i < n:
if not heap:
day = events[i][0]
# Add all events starting today
while i < n and events[i][0] <= day:
heapq.heappush(heap, events[i][1])
i += 1
# Attend earliest-ending event
if heap:
heapq.heappop(heap)
ans += 1; day += 1
return ans
Complexity
- Time: O(n log n)
- Space: O(n)
Advertisement