1353. Maximum Number of Events That Can Be Attended - Detailed Explanation

Problem Statement

You are given an array of events where each event is represented as a two-element array:
events[i] = [startDayᵢ, endDayᵢ].

An event i starts at startDayᵢ and ends at endDayᵢ. You can attend an event on any day d such that startDayᵢ ≤ d ≤ endDayᵢ, but you can attend at most one event per day.

Goal:
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 events:
  • Attend event [1,2] on day 1.
  • Attend event [2,3] on day 2.
  • Attend event [3,4] on day 3.

Example 2

• Input:

  events = [[1,2],[2,3],[3,4],[1,2]]
  

• Output:

  4
  

• Explanation:
  Even though some events overlap, by choosing appropriate days you can attend:
  • Attend one event [1,2] on day 1.
  • Attend the other event [1,2] on day 2 (if possible, after choosing the best order).
  • Then attend [2,3] and [3,4] on subsequent days.

Example 3

• Input:

  events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
  

• Output:

  4
  

• Explanation:
  One way to attend 4 events is:
  • Attend event [1,1] on day 1.
  • Attend event [2,2] on day 2.
  • Attend event [3,4] on day 3.
  • Attend event [4,4] on day 4.

Constraints

• 1 <= events.length <= 10⁵
• 1 <= startDayᵢ <= endDayᵢ <= 10⁵

Hints for the Approach

• Hint 1:
  Since you can attend only one event per day, try to schedule events so that you attend the one that ends the earliest on any given day. This opens up more days for future events.

• Hint 2:
  Sorting events by their start day is useful. Then, use a data structure (like a min-heap) to always pick the event with the smallest end day that is available on a given day.

Approaches

Approach 1: Brute Force (Discussion)

One might consider checking every possible combination of events to see which combination yields the maximum count. For each day, try attending every possible event available and backtrack.
Why it's not ideal:

• The number of events can be as large as 10⁵, making brute force or backtracking solutions computationally infeasible due to exponential time complexity.

Approach 2: Greedy with a Priority Queue (Optimal)

Idea:

1. Sort the Events:
   Sort the events based on their start day. This lets you process events in the order in which they become available.

2. Use a Min-Heap (Priority Queue):
   As you iterate through the days (from the earliest possible day to the maximum end day), do the following:

   • Add all events that start on the current day to the min-heap, where the heap is ordered by the event’s end day.

   • Remove expired events: Remove from the heap any events whose end day is before the current day.

   • Attend an event: If the heap is not empty, attend the event that ends earliest (pop from the heap) and count it as attended.

3. Stop When All Days or Events Are Processed.

This greedy strategy is optimal because by always attending the event that ends the earliest, you leave as much room as possible for subsequent events.

Step-by-Step Walkthrough (Greedy Approach)

Consider the events:

events = [[1,2],[2,3],[3,4],[1,2]]

Step 1: Sort by Start Day
Sorted events:

[[1,2], [1,2], [2,3], [3,4]]

Step 2: Process Days and Use a Min-Heap

• Day 1:

  • Add events starting on day 1 → Heap now contains events with end days 2 and 2.
  • Remove events that ended before day 1 (none in this case).
  • Attend the event with the smallest end day (pop one event with end day 2).
    Count = 1.

• Day 2:

  • Add events starting on day 2 → Heap now contains the remaining event from day 1 (end day 2) and event [2,3] (end day 3).
  • Remove expired events: Remove any event with end day < 2. In this case, events with end day 2 are still valid on day 2.
  • Attend the event with the smallest end day (pop event with end day 2).
    Count = 2.

• Day 3:

  • Add events starting on day 3 → Heap now contains event [2,3] (end day 3) and event [3,4] (end day 4).
  • Remove expired events: Remove events with end day < 3.
    The event with end day 3 is still valid on day 3.
  • Attend the event with the smallest end day (pop event with end day 3).
    Count = 3.

• Day 4:

  • No new events starting on day 4.
  • Heap now contains event [3,4] (end day 4). Remove expired events: It is still valid on day 4.
  • Attend the event with the smallest end day (pop event with end day 4).
    Count = 4.

• Result:
  Maximum events attended = 4.

Pseudocode

sort events by start day
initialize minHeap (empty)
count = 0
i = 0  // index for events

for day from 1 to max_end_day:
    while i < events.length and events[i].start <= day:
        add events[i].end to minHeap
        i++
    while minHeap is not empty and minHeap.peek() < day:
        remove element from minHeap  // remove expired events
    if minHeap is not empty:
        pop from minHeap  // attend the event that ends earliest
        count++

return count

Code Implementation

Python Implementation