Maximum Number of Events Attended — Greedy + Binary Search

Sanjeev SharmaSanjeev Sharma
1 min read

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

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro