Maximum Number of Events That Can Be Attended

Med

#1256Time: 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.4 companies

Patterns

Greedy

Algorithms

Sorting

Data structures

Array Heap (Priority Queue)

Companies

PayPal Snowflake Visa Instacart

Prompt

You are given an array of events where events[i] = [startDay_i, endDay_i]. Every event i starts at startDay_iand ends at endDay_i.

You can attend an event i at any day d where startTime_i <= d <= endTime_i. 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 <= 10⁵
events[i].length == 2
1 <= startDay_i <= endDay_i <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

1. Sort the events array based on the endDay in ascending order.
1. Initialize a set attendedDays to store the days on which an event has been scheduled.
1. Initialize a counter count to 0.
1. Iterate through each event in the sorted array:
1. a. For the current event with [startDay, endDay], iterate from d = startDay to endDay.
1. b. If day d is not in attendedDays:
1. i. Add `d` to `attendedDays`.
1. ii. Increment `count`.
1. iii. Break the inner loop and proceed to the next event.
1. Return count.

Walkthrough

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.

1import java.util.Arrays;2import java.util.HashSet;3 4class Solution {5    public int maxEvents(int[][] events) {6        // Sort events by their end day.7        Arrays.sort(events, (a, b) -> a[1] - b[1]);8 9        HashSet<Integer> attendedDays = new HashSet<>();10        int count = 0;11 12        for (int[] event : events) {13            int startDay = event[0];14            int endDay = event[1];15            // Find the earliest available day for this event.16            for (int d = startDay; d <= endDay; d++) {17                if (!attendedDays.contains(d)) {18                    attendedDays.add(d);19                    count++;20                    break; // Move to the next event21                }22            }23        }24        return count;25    }26}

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.

Complexity

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.

Trade-offs

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.

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.

Algorithm

1. Sort the events array based on the startDay in ascending order.
1. Initialize a min-heap pq to store the end days of active events.
1. Initialize count = 0 and an event pointer i = 0.
1. Iterate through each day d from 1 to the maximum possible day (e.g., 100000).
1. a. Remove all elements from the top of pq that are less than d (these events have expired).
1. b. While the event pointer i is within bounds and events[i][0] == d, add events[i][1] to pq and increment i.
1. 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).
1. Return count.

Walkthrough

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:

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.
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.
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.

1import java.util.Arrays;2import java.util.PriorityQueue;3 4class Solution {5    public int maxEvents(int[][] events) {6        // Sort events by start day7        Arrays.sort(events, (a, b) -> a[0] - b[0]);8 9        // Min-heap to store end days of available events10        PriorityQueue<Integer> pq = new PriorityQueue<>();11        int i = 0; // event pointer12        int count = 0;13        int n = events.length;14        15        // Iterate through all possible days16        for (int d = 1; d <= 100000; d++) {17            // Remove events from the heap that have already ended18            while (!pq.isEmpty() && pq.peek() < d) {19                pq.poll();20            }21 22            // Add new events that start on the current day23            while (i < n && events[i][0] == d) {24                pq.offer(events[i][1]);25                i++;26            }27 28            // If there are available events, attend one29            if (!pq.isEmpty()) {30                pq.poll(); // Attend the one that ends soonest31                count++;32            }33            34            // Optimization: if all events are processed and heap is empty, we can stop35            if (i >= n && pq.isEmpty()) {36                break;37            }38        }39        return count;40    }41}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ; } };

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem