My Solution to LeetCode 1353: Maximum Number of Events That Can Be Attended

Problem Statement

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 startDayi <= d <= endDayi. You can only attend one event at any time d.

Return the maximum number of events you can attend.

Examples

Example 1:

                  Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all three events.
- 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
Explanation: You can attend all four events.
- Attend one [1,2] event on day 1
- Attend another [1,2] event on day 2
- Attend [2,3] event on day 3
- Attend [3,4] event on day 4
                

Understanding the Problem

This is a classic interval scheduling problem with a twist. Unlike traditional interval scheduling, where we pick non-overlapping intervals, here we can attend overlapping events as long as we attend them on different days.

Some Key Insights

1. Greedy Strategy: We should prioritize events that have fewer scheduling options (end sooner)

1. Flexibility: Events with longer durations give us more flexibility in scheduling

1. One Event Per Day: We can only attend one event per day, so we need to make optimal choices

Approach 1: Naive Greedy (Time Limit Exceeded)

Let's start with the intuitive approach to understand the problem better. This was my first approach, but got Time Limit Exceeded

Algorithm

1. Sort events by end day (attend events that end earlier first)

1. For each event, try to attend it on the earliest available day

1. Use a set to track occupied days

Code

                  csharp

public int MaxEvents(int[][] events)
{
// Sort by end day - greedy approach
    Array.Sort(events, (a, b) => a[1].CompareTo(b[1]));

    HashSet<int> occupiedDays = new HashSet<int>();
    int attendedEvents = 0;

    foreach (int[] eventTime in events)
    {
        int startDay = eventTime[0];
        int endDay = eventTime[1];

// Try to find the earliest available day
        for (int day = startDay; day <= endDay; day++)
        {
            if (!occupiedDays.Contains(day))
            {
                occupiedDays.Add(day);
                attendedEvents++;
                break;
            }
        }
    }

    return attendedEvents;
}
                

Why This Gets TLE

The problem occurs when events have large day ranges. Consider an event [1, 100000]; we might have to iterate through up to 100,000 days. With multiple such events, the time complexity becomes O(n × max_duration), which can be huge.

Time Complexity: O(n log n + n × d) where d is the maximum event duration

Space Complexity: O(d) for the HashSet

Approach 2: Optimized Greedy with Priority Queue

The key insight is to avoid iterating through individual days. Instead, we process days sequentially and maintain active events efficiently.

Algorithm

1. Sort events by start day

1. Use a min-heap to track end days of currently active events

1. For each day:

• Add all events that start on or before this day

• Remove events that have already ended

• If there are active events, attend the one that ends earliest

1. Continue until no more events or active events remain

Code

                  csharp

public int MaxEvents(int[][] events)
{
// Sort events by start day
    Array.Sort(events, (a, b) => a[0].CompareTo(b[0]));

// Min heap to store end days of active events
    var minHeap = new PriorityQueue<int, int>();

    int eventIndex = 0;
    int currentDay = 1;
    int attendedEvents = 0;

    while (eventIndex < events.Length || minHeap.Count > 0)
    {
// Add all events that start on or before current day
        while (eventIndex < events.Length && events[eventIndex][0] <= currentDay)
        {
            minHeap.Enqueue(events[eventIndex][1], events[eventIndex][1]);
            eventIndex++;
        }

// Remove events that have already ended
        while (minHeap.Count > 0 && minHeap.Peek() < currentDay)
        {
            minHeap.Dequeue();
        }

// Attend the event that ends earliest
        if (minHeap.Count > 0)
        {
            minHeap.Dequeue();
            attendedEvents++;
        }

        currentDay++;
    }

    return attendedEvents;
}
                

Step-by-Step Walkthrough

Let's trace through Example 1: [[1,2],[2,3],[3,4]]

After sorting by start day: [[1,2],[2,3],[3,4]] (already sorted)

Day 1:

• Add events starting ≤ day 1: [1,2] → heap: [2]

• No expired events

• Attend event ending on day 2 → attendedEvents = 1, heap: []

Day 2:

• Add events starting ≤ day 2: [2,3] → heap: [3]

• No expired events

• Attend event ending on day 3 → attendedEvents = 2, heap: []

Day 3:

• Add events starting ≤ day 3: [3,4] → heap: [4]

• No expired events

• Attend event ending on day 4 → attendedEvents = 3, heap: []

Result: 3 events attended

Time and Space Complexity

Time Complexity: O(n log n)

• Sorting: O(n log n)

• Each event is added and removed from heap once: O(n log n)

• Processing days: O(max_end_day), but each operation is O(log n)

Space Complexity: O(n) for the priority queue

Alternative Implementation (For Older .NET Versions)

If you're using .NET versions before 6.0 that don't have PriorityQueue, you can use SortedSet:

                  csharp

public int MaxEvents(int[][] events)
{
    Array.Sort(events, (a, b) => a[0].CompareTo(b[0]));

    var activeEvents = new SortedSet<int>();
    int eventIndex = 0;
    int currentDay = 1;
    int attendedEvents = 0;

    while (eventIndex < events.Length || activeEvents.Count > 0)
    {
// Add events starting on or before current day
        while (eventIndex < events.Length && events[eventIndex][0] <= currentDay)
        {
            activeEvents.Add(events[eventIndex][1]);
            eventIndex++;
        }

// Remove expired events
        activeEvents.RemoveWhere(endDay => endDay < currentDay);

// Attend earliest ending event
        if (activeEvents.Count > 0)
        {
            int earliestEndDay = activeEvents.Min;
            activeEvents.Remove(earliestEndDay);
            attendedEvents++;
        }

        currentDay++;
    }

    return attendedEvents;
}
                

Conclusion

This problem quite beautifully demonstrates the power of greedy algorithms and the importance of choosing the right data structures. The key insight is recognizing that we should prioritize events with less flexibility (earlier end times) and using efficient data structures to avoid unnecessary iterations.

The optimized solution transforms a potentially O(n × d) algorithm into an O(n log n) solution, making it capable of handling large inputs efficiently. Just remember, sometimes the first solution that works isn't the most efficient, always consider the time complexity and optimize when necessary.

Read more at: Lazzerex’s Blog