Problem Description

You have a list of events, where each event is represented by a start day and an end day. Each event i is given as [startDay_i, endDay_i], meaning the event starts on startDay_i and ends on endDay_i.

You can attend an event on any day during its duration - that is, you can attend event i on any day d where startDay_i ≤ d ≤ endDay_i. However, there's an important constraint: you can only attend one event per day.

Your goal is to find the maximum number of events you can attend.

For example, if you have events [[1,2], [2,3], [3,4]]:

• Event 1 runs from day 1 to day 2
• Event 2 runs from day 2 to day 3
• Event 3 runs from day 3 to day 4

You could attend all 3 events by:

• Attending event 1 on day 1
• Attending event 2 on day 2
• Attending event 3 on day 3

The key insight is that for each day, if multiple events are available, you should greedily choose to attend the event that will end soonest. This maximizes your future options for attending other events.

Intuition

The key observation is that we need to make optimal decisions about which event to attend on each day. If multiple events are available on a given day, which one should we choose?

Consider this scenario: on day 2, we have two events available - one ending on day 3 and another ending on day 7. If we choose the event ending on day 7, we might miss the opportunity to attend the event ending on day 3 (since it will expire soon). However, if we choose the event ending on day 3, we still have more days to attend the other event.

This leads us to a greedy strategy: always attend the event that will end soonest. By doing this, we minimize the risk of missing events that are about to expire.

To implement this strategy efficiently, we need to:

1. Process days in chronological order
2. Keep track of which events become available on each day
3. Among all available events on a given day, pick the one with the earliest end time

A priority queue (min-heap) is perfect for this - it allows us to efficiently track all currently available events sorted by their end times. As we move through each day:

• We add any events that start on that day to our pool of available events
• We remove any events that have already expired (ended before the current day)
• We attend the event with the earliest end time from our available pool

This greedy approach ensures we maximize the number of events attended because we're always prioritizing events that have less flexibility in when they can be attended.

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation uses a hash table combined with a greedy algorithm and a priority queue to solve this problem efficiently.

Step 1: Organize Events by Start Time

First, we create a hash table g where the key is the start day and the value is a list of end days for all events starting on that day. We also track the minimum start day l and maximum end day r across all events:

g = defaultdict(list)
l, r = inf, 0
for s, e in events:
    g[s].append(e)
    l = min(l, s)
    r = max(r, e)

This preprocessing allows us to quickly access all events that become available on any given day.

Step 2: Process Each Day Sequentially

We iterate through each day from l to r and maintain a min-heap pq that stores the end times of all currently available events:

pq = []
ans = 0
for s in range(l, r + 1):

Step 3: Remove Expired Events

For each day s, we first remove all events that have already expired (their end time is before the current day):

while pq and pq[0] < s:
    heappop(pq)

Step 4: Add Newly Available Events

We add all events that start on the current day s to our priority queue:

for e in g[s]:
    heappush(pq, e)

Step 5: Attend the Best Event

If there are any available events, we attend the one with the earliest end time (the minimum element in our heap) and increment our answer:

if pq:
    heappop(pq)
    ans += 1

By removing this event from the queue, we ensure we don't try to attend it again on a future day.

The algorithm ensures that at each day, we make the optimal greedy choice by attending the event that will expire soonest, maximizing the total number of events we can attend. The time complexity is O(n log n) where n is the total number of days in the range, and the space complexity is O(m) where m is the number of events.

Example Walkthrough

Let's walk through the solution with a concrete example: events = [[1,4], [4,4], [2,2], [3,4], [1,1]]

Step 1: Organize Events by Start Time

First, we create our hash table g and find the range of days:

• Event [1,4]: starts day 1, ends day 4
• Event [4,4]: starts day 4, ends day 4
• Event [2,2]: starts day 2, ends day 2
• Event [3,4]: starts day 3, ends day 4
• Event [1,1]: starts day 1, ends day 1

Our hash table g becomes:

g = {
    1: [4, 1],  # Two events start on day 1
    2: [2],     # One event starts on day 2
    3: [4],     # One event starts on day 3
    4: [4]      # One event starts on day 4
}

Range: l = 1, r = 4

Step 2-5: Process Each Day

Day 1:

• Priority queue (min-heap) starts empty: pq = []
• No expired events to remove
• Add events starting on day 1: pq = [1, 4] (sorted by end time)
• Attend event ending on day 1: heappop(pq) removes 1
• pq = [4], ans = 1

Day 2:

• Current pq = [4]
• Remove expired events: 4 ≥ 2, so nothing removed
• Add events starting on day 2: heappush(pq, 2)
• pq = [2, 4] (heap maintains min property)
• Attend event ending on day 2: heappop(pq) removes 2
• pq = [4], ans = 2

Day 3:

• Current pq = [4]
• Remove expired events: 4 ≥ 3, so nothing removed
• Add events starting on day 3: heappush(pq, 4)
• pq = [4, 4] (two events both ending on day 4)
• Attend one event ending on day 4: heappop(pq) removes one 4
• pq = [4], ans = 3

Day 4:

• Current pq = [4]
• Remove expired events: 4 ≥ 4, so nothing removed
• Add events starting on day 4: heappush(pq, 4)
• pq = [4, 4]
• Attend one event ending on day 4: heappop(pq) removes one 4
• pq = [4], ans = 4

Final Result: We attended 4 events total.

The greedy strategy worked perfectly here - by always choosing the event that ends soonest, we were able to attend:

• Day 1: Event [1,1]
• Day 2: Event [2,2]
• Day 3: Event [3,4] or [1,4]
• Day 4: Event [4,4]

Solution Implementation

Time and Space Complexity

Time Complexity: O(M × log n), where M is the range of days from the minimum start day to the maximum end day of all events, and n is the number of events.

• The initial loop to build the graph and find min/max days takes O(n) time
• The main loop iterates through each day from l to r, which is O(M) iterations
• Within each day:
  • The while loop for removing expired events performs at most n total heap pops across all iterations, each taking O(log n) time
  • Adding events that start on day s involves heap push operations, with at most n total pushes across all days, each taking O(log n) time
  • Attending an event (if available) involves one heap pop, taking O(log n) time
• Overall: O(M) iterations × O(log n) operations per iteration = O(M × log n)

Space Complexity: O(n), where n is the number of events.

• The dictionary g stores all events grouped by start day, using O(n) space
• The priority queue pq can contain at most n events at any given time, using O(n) space
• Other variables use O(1) space
• Total space complexity: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Day Range Iteration for Sparse Events

The current solution iterates through every single day from min_start_day to max_end_day. When events are sparse (e.g., events at days 1 and 100000 only), this creates unnecessary iterations through empty days, leading to poor performance.

Example problematic case:

events = [[1, 1], [100000, 100000]]
# The algorithm iterates through 99,999 days unnecessarily

Solution: Instead of iterating through all days, only process days where events actually start or could be attended:

def maxEvents(self, events: List[List[int]]) -> int:
    events.sort()  # Sort by start day
    available_events = []
    attended_events = 0
    day = 0
    i = 0
  
    while i < len(events) or available_events:
        # If no available events, jump to next event's start day
        if not available_events:
            day = events[i][0]
      
        # Add all events starting on current day
        while i < len(events) and events[i][0] <= day:
            heappush(available_events, events[i][1])
            i += 1
      
        # Remove expired events
        while available_events and available_events[0] < day:
            heappop(available_events)
      
        # Attend event ending soonest
        if available_events:
            heappop(available_events)
            attended_events += 1
            day += 1
  
    return attended_events

2. Memory Overhead from Dictionary Storage

Using defaultdict(list) to group events by start day can consume significant memory when there are many unique start days. Additionally, accessing dictionary keys has overhead compared to sorted array traversal.

Solution: Sort the events array directly and process them in order, eliminating the need for the dictionary:

events.sort(key=lambda x: x[0])  # Sort by start day
# Process events sequentially without dictionary

3. Not Handling Edge Cases with Overlapping Single-Day Events

When multiple events occur on the same single day (e.g., [[1,1], [1,1], [1,1]]), the algorithm correctly handles this by only attending one. However, developers might incorrectly assume they need special handling for this case, leading to overly complex code.

Key insight: The existing greedy approach naturally handles this case - only one event can be popped from the heap per day, regardless of how many single-day events exist on that day.