Skip to main content
Talentd

Maximum Number of Events That Can Be Attended - Solution & Explanation

MediumArrayGreedySortingHeap (Priority Queue)18 min readAsked at: Amazon, Microsoft, Goldman Sachs +13
Practice this problem

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 startTimei <= d <= endTimei. 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 <= 105
  • events[i].length == 2
  • 1 <= startDayi <= endDayi <= 105

Approach Overview

Problem Overview: You are given an array where events[i] = [startDay, endDay]. Each event can be attended on any single day within its range. The goal is to attend the maximum number of events without attending more than one event per day.

Approach 1: Greedy with Sorting and Set (Time: O(n log n + D log D), Space: O(D))

This approach uses a greedy scheduling idea. First sort the events by their ending day so that events that expire earlier are considered first. Maintain a sorted set of available days (typically from 1 to maxDay). For each event, use a set operation such as lower_bound to find the earliest available day that is greater than or equal to its start day. If that day is within the event's end day, attend the event and remove the day from the set.

The key insight is simple: always occupy the earliest valid day for an event so later days remain available for other events. Sorting ensures events that expire sooner get priority. This method relies heavily on ordered set operations and works well when the day range is manageable.

Approach 2: Priority Queue (Min-Heap) Method (Time: O(n log n), Space: O(n))

This is the most common and scalable solution. Start by sorting events by their start day. Iterate through days in increasing order and maintain a min-heap that stores the end days of events that have already started but not yet been attended. When the current day reaches an event's start day, push its end day into the heap.

At each day, remove events from the heap whose end day is earlier than the current day because they are already expired. Then attend the event with the smallest end day by popping the heap. Choosing the event that ends earliest prevents losing opportunities for short intervals. Each event is inserted and removed from the heap at most once, giving an efficient O(n log n) runtime.

This approach combines greedy scheduling with a heap (priority queue) while relying on initial sorting. It handles large day ranges efficiently because it only processes relevant events rather than tracking every possible day explicitly.

Recommended for interviews: The priority queue solution is what most interviewers expect. It demonstrates understanding of greedy scheduling and efficient event selection using a min-heap. Mentioning the set-based greedy idea shows good intuition, but implementing the heap approach proves you can manage dynamic candidate events efficiently with O(n log n) complexity.

Approach 1: Approach 1: Greedy Approach with Sorting and Set

The idea is to sort the events by their end days. By doing this, you give preference to events that finish earliest, thus maximizing the number of events you can attend. You use a set to record which days are occupied. For each event, try to attend it on the earliest possible day starting from the event's start day.

The solution begins by sorting the events on their end days. We then iterate over the events and try to attend them at the earliest possible day that is still unoccupied. A boolean array is used to mark the days that have been occupied. This helps efficiently manage which days have been taken up by events, ensuring that no two events are attended on the same day.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N log N), where N is the number of events, due to sorting.
Space Complexity: O(1), considering the constraint that the maximum day value does not exceed 100,000.

Try this approach in the editor →

Approach 2: Approach 2: Priority Queue (Min-Heap) Method

In this approach, we leverage a priority queue (implemented using a min-heap) to choose the next event to attend. By adding each event's end day to the heap, we can focus on attending the event that ends first among the available ones. We iterate over the days and use the priority queue to ensure the event attended finishes at the earliest possible time, freeing up subsequent days for potentially more events.

The C++ solution uses a priority queue to manage events by their end times. By popping the smallest element (earliest end time), the code guarantees that it tries to attend the event that leaves most days open for future events, allowing more to be attended overall.

Code

C++Python

C++

Python

Complexity

Time Complexity: O(N log N), with N log N for sorting and N log N for priority queue operations.
Space Complexity: O(N) for the priority queue.

Try this approach in the editor →

Approach 3: Hash Table + Greedy + Priority Queue

We use a hash table g to record the start and end times of each event. The key is the start time of the event, and the value is a list containing the end times of all events that start at that time. Two variables, l and r, are used to record the minimum start time and the maximum end time among all events.

For each time point s from l to r in increasing order, we perform the following steps:

  1. Remove from the priority queue all events whose end time is less than the current time s.
  2. Add the end times of all events that start at the current time s to the priority queue.
  3. If the priority queue is not empty, take out the event with the earliest end time, increment the answer count, and remove this event from the priority queue.

In this way, we ensure that at each time point s, we always attend the event that ends the earliest, thus maximizing the number of events attended.

The time complexity is O(M times log n), and the space complexity is O(n), where M is the maximum end time and n is the number of events.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Greedy Approach with Sorting and Set

Time Complexity: O(N log N), where N is the number of events, due to sorting.
Space Complexity: O(1), considering the constraint that the maximum day value does not exceed 100,000.

Approach 2: Priority Queue (Min-Heap) Method

Time Complexity: O(N log N), with N log N for sorting and N log N for priority queue operations.
Space Complexity: O(N) for the priority queue.

Hash Table + Greedy + Priority Queue—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Sorting and Ordered SetO(n log n + D log D)O(D)Useful when the day range is small and an ordered set of available days can be maintained efficiently.
Greedy with Min-Heap (Priority Queue)O(n log n)O(n)Best general solution for interviews and large inputs. Dynamically tracks active events and always selects the one ending earliest.

Video Solution

Leetcode 1353. Maximum Number of Events That Can Be Attended • Fraz • 34,343 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Number of Events That Can Be Attended easy or hard?
Maximum Number of Events That Can Be Attended is rated Medium difficulty on LeetCode. The challenge comes from recognizing the greedy scheduling pattern and combining sorting with a priority queue to efficiently select the next event.
Maximum Number of Events That Can Be Attended Python/Java solution
In Python, the typical solution uses the heapq module to maintain a min-heap of end days while iterating through sorted events. Java implementations use PriorityQueue for the same purpose. Both follow the same greedy idea: always attend the event that ends earliest among currently available events.
How to solve Maximum Number of Events That Can Be Attended in O(n)?
A strict O(n) solution is not practical because events must be processed in chronological order and prioritized by ending time. Sorting and heap operations are required, leading to an optimal complexity of O(n log n). Attempts to remove sorting generally fail when event ranges overlap heavily.
What is the best approach for Maximum Number of Events That Can Be Attended?
The best approach is a greedy algorithm combined with a min-heap (priority queue). Sort events by start day, add active events to a heap ordered by end day, and attend the event that finishes earliest each day. This strategy avoids losing short-duration events and runs in O(n log n) time.
Is Maximum Number of Events That Can Be Attended asked at Google/Amazon/Meta?
This problem represents a classic interval scheduling pattern frequently used in technical interviews. Variations of event scheduling with greedy and priority queue logic have appeared in interviews at companies such as Google, Amazon, and Meta.
What data structure is used in Maximum Number of Events That Can Be Attended?
The optimal solution uses a min-heap (priority queue) to track active events by their end day. Some implementations also use ordered sets or balanced binary search trees to track available days when applying a greedy scheduling strategy.
What is the time complexity of Maximum Number of Events That Can Be Attended?
The optimal solution runs in O(n log n) time. Sorting the events takes O(n log n), and each event is inserted and removed from the min-heap at most once, which adds another O(n log n). Space complexity is O(n) due to the heap storing active events.

Ready to solve this problem?

Practice Maximum Number of Events That Can Be Attended with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Earnings From Taxi

Next

Maximum Number of Events That Can Be Attended II