Maximum Number of Events That Can Be Attended solution and explanation
Google
9 more videos on this problem
Leetcode 1353. Maximum Number of Events That Can Be AttendedFraz · 11:50 · 34K views
Maximum Number of Events That Can Be Attended | Detailed Approach | Leetcode 1353 | codestorywithMIKcodestorywithMIK · 28:04 · 22K views
Maximum Number of Events That Can Be Attended | Leetcode - 1353Algorithms Made Easy · 15:10 · 13K views
Maximum Number of Events That Can Be Attended | Leetcode 1353Techdose · 14:27 · 9K views
LeetCode 1353. Maximum Number of Events That Can Be AttendedHappy Coding · 26:47 · 8K views
1353. Maximum Number of Events That Can Be Attended: LeetCode SolutionviralSongs · 8:58 · 4K views
1353. Maximum Number of Events That Can Be Attended | Leetcode Daily - PythonLeetcode Daily · 4:27 · 2K views
Daily Leetcode #1924: Jul 07, 2025 - 1353. Maximum Number of Events That Can Be AttendedProgramming Live with Larry · 15:22 · 1K views
LeetCode | 1353. Maximum Number of Events That Can Be Attended | Priority Queue | MinHeapCompl3x · 13:10 · 1K views
Maximum Number of Events That Can Be Attended | LeetCode 1353 - Pythonimpoldev · 9:38 · 619 views
The 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:
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 <= 105events[i].length == 21 <= 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.
def maxEvents(events):
events.sort(key=lambda x: x[1])
attended_days = set()
for start, end in events:
for d in range(start, end + 1):
if d not in attended_days:
attended_days.add(d)
break
return len(attended_days)import java.util.*;
class Solution {
public int maxEvents(int[][] events) {
Arrays.sort(events, (a, b) -> a[1] - b[1]);
Set<Integer> attended = new HashSet<>();
for (int[] event : events) {
for (int d = event[0]; d <= event[1]; d++) {
if (attended.add(d)) {
break;
}
}
}
return attended.size();
}
}#include <vector>
#include <algorithm>
#include <set>
using namespace std;
class Solution {
public:
int maxEvents(vector<vector<int>>& events) {
sort(events.begin(), events.end(), [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
});
set<int> attended;
int maxDay = 0;
for (auto& event : events) {
for (int d = event[0]; d <= event[1]; ++d) {
if (attended.insert(d).second) { // Insert operation returns true if insertion is done successfully
break;
}
}
}
return attended.size();
}
};const maxEvents = function(events) {
events.sort((a, b) => a[1] - b[1]);
const attendedDays = new Set();
for (let [start, end] of events) {
for (let d = start; d <= end; d++) {
if (!attendedDays.has(d)) {
attendedDays.add(d);
break;
}
}
}
return attendedDays.size;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int cmp(const void *a, const void *b) {
int *x = (int *)a;
int *y = (int *)b;
if (x[1] == y[1])
return x[0] - y[0];
return x[1] - y[1];
}
int maxEvents(int** events, int eventsSize, int* eventsColSize) {
qsort(events, eventsSize, sizeof(events[0]), cmp);
bool days[100001] = {false};
int count = 0;
for (int i = 0; i < eventsSize; i++) {
for (int d = events[i][0]; d <= events[i][1]; d++) {
if (!days[d]) {
days[d] = true;
count++;
break;
}
}
}
return count;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxEvents(int[][] events) {
Array.Sort(events, (a, b) => a[1] - b[1]);
HashSet<int> attended = new HashSet<int>();
foreach (var ev in events) {
for (int d = ev[0]; d <= ev[1]; d++) {
if (attended.Add(d)) {
break;
}
}
}
return attended.Count;
}
}The Python solution leverages a set to keep track of attended days. It sorts events first by end days and uses nested loops to find the earliest available day for each event within its period.
Time Complexity: O(N log N) for sorting, with O(N) possible operations to fill the set.
Space Complexity: O(N) for storing days in the set.
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.
import heapq
def maxEvents(events):
events.sort()
min_heap = []
i = 0
res = 0
day = 0
while i < len(events) or min_heap:
if not min_heap:
day = events[i][0]
while i < len(events) and events[i][0] <= day:
heapq.heappush(min_heap, events[i][1])
i += 1
heapq.heappop(min_heap)
res += 1
day += 1
while min_heap and min_heap[0] < day:
heapq.heappop(min_heap)
return res#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
class Solution {
public:
int maxEvents(vector<vector<int>>& events) {
sort(events.begin(), events.end());
priority_queue<int, vector<int>, greater<int>> pq;
int i = 0, day = 0, res = 0, n = events.size();
while (i < n || !pq.empty()) {
if (pq.empty()) day = events[i][0];
while (i < n && events[i][0] <= day)
pq.push(events[i++][1]);
pq.pop();
res++;
day++;
while (!pq.empty() && pq.top() < day)
pq.pop();
}
return res;
}
};The Python solution sorts events and uses a heap (min-heap) to keep track of events' end days. You iterate over each day and use the heap to prioritize attending events that leave the most future days open.
Time Complexity: O(N log N) due to sorting and heap operations.
Space Complexity: O(N) for the heap.
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:
- Remove from the priority queue all events whose end time is less than the current time
s. - Add the end times of all events that start at the current time
sto the priority queue. - 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.
function maxEvents(events: number[][]): number {
const g: Map<number, number[]> = new Map();
let l = Infinity,
r = 0;
for (const [s, e] of events) {
if (!g.has(s)) g.set(s, []);
g.get(s)!.push(e);
l = Math.min(l, s);
r = Math.max(r, e);
}
const pq = new MinPriorityQueue<number>();
let ans = 0;
for (let s = l; s <= r; s++) {
while (!pq.isEmpty() && pq.front() < s) {
pq.dequeue();
}
for (const e of g.get(s) || []) {
pq.enqueue(e);
}
if (!pq.isEmpty()) {
pq.dequeue();
ans++;
}
}
return ans;
}func maxEvents(events [][]int) (ans int) {
g := map[int][]int{}
l, r := math.MaxInt32, 0
for _, event := range events {
s, e := event[0], event[1]
g[s] = append(g[s], e)
l = min(l, s)
r = max(r, e)
}
pq := &hp{}
heap.Init(pq)
for s := l; s <= r; s++ {
for pq.Len() > 0 && pq.IntSlice[0] < s {
heap.Pop(pq)
}
for _, e := range g[s] {
heap.Push(pq, e)
}
if pq.Len() > 0 {
heap.Pop(pq)
ans++
}
}
return
}
type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
n := len(h.IntSlice)
v := h.IntSlice[n-1]
h.IntSlice = h.IntSlice[:n-1]
return v
}
func (h *hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }use std::collections::{BinaryHeap, HashMap};
use std::cmp::Reverse;
impl Solution {
pub fn max_events(events: Vec<Vec<i32>>) -> i32 {
let mut g: HashMap<i32, Vec<i32>> = HashMap::new();
let mut l = i32::MAX;
let mut r = 0;
for event in events {
let s = event[0];
let e = event[1];
g.entry(s).or_default().push(e);
l = l.min(s);
r = r.max(e);
}
let mut pq = BinaryHeap::new();
let mut ans = 0;
for s in l..=r {
while let Some(&Reverse(top)) = pq.peek() {
if top < s {
pq.pop();
} else {
break;
}
}
if let Some(ends) = g.get(&s) {
for &e in ends {
pq.push(Reverse(e));
}
}
if pq.pop().is_some() {
ans += 1;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Approach with Sorting and Set | Time Complexity: O(N log N) for sorting, with O(N) possible operations to fill the set. |
| Approach 2: Priority Queue (Min-Heap) Method | Time Complexity: O(N log N) due to sorting and heap operations. |
| Hash Table + Greedy + Priority Queue | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting and Ordered Set | O(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. |
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.