{x}
blog image

Maximum Number of Events That Can Be Attended

You are given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.

You can attend an event i at any day d where startTimei <= d <= endTimei. You can only attend one event at any time d.

Return the maximum number of events you can attend.

 

Example 1:

Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: 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.

Example 2:

Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4

 

Constraints:

  • 1 <= events.length <= 105
  • events[i].length == 2
  • 1 <= startDayi <= endDayi <= 105

Solution Explanation: Maximum Number of Events That Can Be Attended

This problem asks to find the maximum number of events that can be attended, given a list of events with start and end days. We can only attend one event per day.

The optimal approach involves a combination of sorting, greedy selection, and a priority queue (min-heap).

1. Sorting:

First, we sort the events by their start days. This allows us to process events in chronological order.

2. Greedy Selection and Priority Queue:

We use a min-heap (priority queue) to store the end days of events that are currently "available" to attend. "Available" means the event's start day is less than or equal to the current day, and the event has not yet ended.

We iterate through the days (from the minimum start day to the maximum end day). For each day:

  • Remove Ended Events: We remove from the priority queue any events whose end day is earlier than the current day. These events are no longer candidates.
  • Add Starting Events: We add the end days of all events that start on the current day to the priority queue.
  • Attend an Event: If the priority queue is not empty, we greedily select the event with the earliest end day (the top of the min-heap). We attend this event and increment our counter. This greedy choice is optimal because attending the event that ends earliest frees up the day the soonest for potential future events.

Time Complexity Analysis:

  • Sorting the events takes O(N log N) time, where N is the number of events.
  • Iterating through the days takes O(M) time, where M is the maximum end day. In the worst case, M can be O(N), but generally, it's much smaller than the number of events.
  • Adding and removing events from the priority queue takes O(log K) time per operation, where K is the number of events in the priority queue at any given time. K is at most N.
  • Therefore, the overall time complexity is dominated by the sorting step and the priority queue operations, resulting in O(N log N) time complexity.

Space Complexity Analysis:

  • We use a priority queue to store end days, which can hold up to N events in the worst case.
  • Thus, the space complexity is O(N).

Code Implementation (Python):

import heapq
 
def maxEvents(events):
    events.sort()  # Sort events by start day
    pq = []  # Min-heap to store end days of available events
    count = 0
    i = 0
    day = 1  # Current day
    while i < len(events) or pq:
        while i < len(events) and events[i][0] == day:
            heapq.heappush(pq, events[i][1])
            i += 1
        while pq and pq[0] < day:
            heapq.heappop(pq)
        if pq:
            heapq.heappop(pq)
            count += 1
        day += 1
    return count

The code in other languages (Java, C++, Go) follows a very similar structure, using their respective implementations of priority queues. The core algorithm remains the same.