# Maximum Number of Events That Can Be Attended
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-events-that-can-be-attended
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal), [Snowflake](https://scaleengineer.com/companies/snowflake), [Visa](https://scaleengineer.com/companies/visa), [Instacart](https://scaleengineer.com/companies/instacart)
---
## Problem
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:**

![](https://assets.glich.co/dsa/maximum-number-of-events-that-can-be-attended/image0.png) 

**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`

# Approaches
## Greedy Approach with Sorting by End Day
This approach uses a greedy strategy. The core idea is to prioritize events that finish earlier. By attending events that are about to expire, we leave more flexibility for events that last longer. We sort the events by their end day. Then, for each event, we try to attend it on the earliest possible day available within its time window.
**Time:** O(N*D + N log N), where N is the number of events and D is the maximum range of days for an event. Sorting takes O(N log N). The nested loops can take up to O(N * D) in the worst case, for example, if all events are `[1, 100000]`. This leads to Time Limit Exceeded on larger test cases. · **Space:** O(D_max), where D_max is the maximum end day among all events. This is for the `attendedDays` set or boolean array. Given the constraints, this is acceptable.
**Pros:** The logic is relatively straightforward to understand.; It correctly implements a valid greedy strategy.
**Cons:** The time complexity is too high due to the linear scan for an available day for each event, making it inefficient for the given constraints.
### Explanation
The algorithm first sorts all events in ascending order of their `endDay`. This is a crucial greedy choice: we always deal with the events that are closest to their deadline.

We then iterate through these sorted events. For each event `[startDay, endDay]`, we try to find an available day to attend it.

To maximize our chances for future events, we should use the earliest possible day for the current event. Therefore, we scan from `startDay` to `endDay`.

We use a boolean array or a hash set, let's call it `usedDays`, to keep track of the days on which we've already scheduled an event.

For the current event, we look for the first day `d` in its range `[startDay, endDay]` such that `usedDays[d]` is false. If we find such a day, we 'attend' the event on day `d` by setting `usedDays[d]` to true, incrementing our count of attended events, and moving on to the next event.

If we iterate through the entire range `[startDay, endDay]` and find no available days, we cannot attend this event and simply move to the next one.

```java
import java.util.Arrays;
import java.util.HashSet;

class Solution {
    public int maxEvents(int[][] events) {
        // Sort events by their end day.
        Arrays.sort(events, (a, b) -> a[1] - b[1]);

        HashSet<Integer> attendedDays = new HashSet<>();
        int count = 0;

        for (int[] event : events) {
            int startDay = event[0];
            int endDay = event[1];
            // Find the earliest available day for this event.
            for (int d = startDay; d <= endDay; d++) {
                if (!attendedDays.contains(d)) {
                    attendedDays.add(d);
                    count++;
                    break; // Move to the next event
                }
            }
        }
        return count;
    }
}
```

The provided code uses a `HashSet` to track attended days. A boolean array could also be used if the maximum day is known and within reasonable memory limits, which might offer slightly better performance for lookups.
### Algorithm
- 1. Sort the `events` array based on the `endDay` in ascending order.
- 2. Initialize a set `attendedDays` to store the days on which an event has been scheduled.
- 3. Initialize a counter `count` to 0.
- 4. Iterate through each `event` in the sorted array:
- 5.    a. For the current `event` with `[startDay, endDay]`, iterate from `d = startDay` to `endDay`.
- 6.    b. If day `d` is not in `attendedDays`:
- 7.       i. Add `d` to `attendedDays`.
- 8.       ii. Increment `count`.
- 9.       iii. Break the inner loop and proceed to the next event.
- 10. Return `count`.

## Optimized Greedy Approach with Min-Heap
This is a more efficient greedy approach that processes the events day by day. Instead of iterating through events, we iterate through time (days). We use a min-heap to keep track of all events that have started but have not yet been attended. The greedy choice at each day is to attend the available event that finishes the soonest, as this leaves events that last longer available for future days.
**Time:** O(N log N + D), where N is the number of events and D is the range of days. Sorting takes O(N log N). The main loop runs D times. Each event is pushed and popped from the heap exactly once, contributing O(N log N) over all iterations. Thus, the total time complexity is dominated by sorting and the day loop, resulting in O(N log N + D). · **Space:** O(N) in the worst case. The min-heap can store up to N events if all events start on the same day.
**Pros:** Highly efficient and passes the given constraints.; The greedy choice is optimal and guarantees the correct maximum number of events.
**Cons:** The logic is slightly more complex than the naive greedy approach, involving a heap and careful iteration over days.
### Explanation
The key idea is to iterate through each day `d` from the first possible start day to the last possible end day.

First, we sort the events by their `startDay`. This allows us to efficiently find all events that become available on a given day `d`.

We use a min-heap (PriorityQueue in Java) to store the `endDay` of events that are currently available. An event is available if its `startDay` has passed, and we haven't attended it yet.

The algorithm proceeds as follows:
We iterate `d` from 1 up to the maximum possible day. An event pointer `i` tracks our position in the sorted `events` array.

On each day `d`:
1. **Add new events:** We add the `endDay` of all events that start on day `d` into the min-heap. We advance the event pointer `i` accordingly.
2. **Remove expired events:** We remove any `endDay` from the top of the heap if `endDay < d`. These represent events that we can no longer attend because their window has closed.
3. **Attend an event:** If the heap is not empty after the cleanup, it means there's at least one valid event we can attend today. We greedily choose the one that ends the soonest (which is at the top of the min-heap). We increment our attended events `count` and remove that event's `endDay` from the heap.

This process ensures that on any given day, we prioritize the most urgent event, which is a powerful greedy strategy that leads to the optimal solution.

```java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int maxEvents(int[][] events) {
        // Sort events by start day
        Arrays.sort(events, (a, b) -> a[0] - b[0]);

        // Min-heap to store end days of available events
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int i = 0; // event pointer
        int count = 0;
        int n = events.length;
        
        // Iterate through all possible days
        for (int d = 1; d <= 100000; d++) {
            // Remove events from the heap that have already ended
            while (!pq.isEmpty() && pq.peek() < d) {
                pq.poll();
            }

            // Add new events that start on the current day
            while (i < n && events[i][0] == d) {
                pq.offer(events[i][1]);
                i++;
            }

            // If there are available events, attend one
            if (!pq.isEmpty()) {
                pq.poll(); // Attend the one that ends soonest
                count++;
            }
            
            // Optimization: if all events are processed and heap is empty, we can stop
            if (i >= n && pq.isEmpty()) {
                break;
            }
        }
        return count;
    }
}
```
### Algorithm
- 1. Sort the `events` array based on the `startDay` in ascending order.
- 2. Initialize a min-heap `pq` to store the end days of active events.
- 3. Initialize `count = 0` and an event pointer `i = 0`.
- 4. Iterate through each day `d` from 1 to the maximum possible day (e.g., 100000).
- 5.    a. Remove all elements from the top of `pq` that are less than `d` (these events have expired).
- 6.    b. While the event pointer `i` is within bounds and `events[i][0] == d`, add `events[i][1]` to `pq` and increment `i`.
- 7.    c. If `pq` is not empty, it means we can attend an event today. Increment `count` and remove the top element from `pq` (attending the event that ends soonest).
- 8. Return `count`.

# Solutions
### Java

```java
class Solution { public int maxEvents ( int [][] events ) { Map < Integer , List < Integer >> d = new HashMap <>(); int i = Integer . MAX_VALUE , j = 0 ; for ( var v : events ) { int s = v [ 0 ], e = v [ 1 ]; d . computeIfAbsent ( s , k -> new ArrayList <>()). add ( e ); i = Math . min ( i , s ); j = Math . max ( j , e ); } PriorityQueue < Integer > q = new PriorityQueue <>(); int ans = 0 ; for ( int s = i ; s <= j ; ++ s ) { while (! q . isEmpty () && q . peek () < s ) { q . poll (); } for ( int e : d . getOrDefault ( s , Collections . emptyList ())) { q . offer ( e ); } if (! q . isEmpty ()) { q . poll (); ++ ans ; } } return ans ; } }
```

### CPP

```cpp
class Solution { public: int maxEvents ( vector < vector < int >>& events ) { unordered_map < int , vector < int >> d ; int i = INT_MAX , j = 0 ; for ( auto & v : events ) { int s = v [ 0 ], e = v [ 1 ]; d [ s ]. push_back ( e ); i = min ( i , s ); j = max ( j , e ); } priority_queue < int , vector < int > , greater < int >> q ; int ans = 0 ; for ( int s = i ; s <= j ; ++ s ) { while ( q . size () && q . top () < s ) { q . pop (); } for ( int e : d [ s ]) { q . push ( e ); } if ( q . size ()) { ++ ans ; q . pop (); } } return ans ; } };
```

### Python

```python
class Solution : def maxEvents ( self , events : List [ List [ int ]]) -> int : d = defaultdict ( list ) i , j = inf , 0 for s , e in events : d [ s ]. append ( e ) i = min ( i , s ) j = max ( j , e ) h = [] ans = 0 for s in range ( i , j + 1 ): while h and h [ 0 ] < s : heappop ( h ) for e in d [ s ]: heappush ( h , e ) if h : ans += 1 heappop ( h ) return ans
```