Maximum Number of Events That Can Be Attended
Maximum Number of Events That Can Be Attended is a medium heaps problem solved with the advanced pattern.
The best approach, optimal (day sweep with a min-heap of end days), runs in O(n log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (earliest deadline, scan for a free day) up.
Problem
You are given a list events where events[i] = [start_i, end_i] means event i can be attended on any single whole day d with start_i <= d <= end_i.
You can attend at most one event per day, and attending an event takes just one day of its range. Return the maximum number of events you can attend.
Examples
Example 1
- Input
events = [[1, 2], [1, 2], [1, 2]]- Output
2- Why
- Only days 1 and 2 exist for these three events, so at most two of them can be attended.
Example 2
- Input
events = [[2, 4], [1, 1], [1, 3], [3, 3]]- Output
4- Why
- Go to [1, 1] on day 1, [1, 3] on day 2, [3, 3] on day 3 and [2, 4] on day 4.
Example 3
- Input
events = [[5, 5], [1, 10]]- Output
2- Why
- Attend [1, 10] on any day except 5 and [5, 5] on day 5.
Constraints
1 <= events.length <= 10^5events[i].length == 21 <= start_i <= end_i <= 10^5
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (earliest deadline, scan for a free day) | O(n log n + n · D) | O(D) |
| Optimal (day sweep with a min-heap of end days) | O(n log n) | O(n) |
1Brute force (earliest deadline, scan for a free day)
O(n log n + n · D)Sorting, then each event may scan its whole range of up to D = 10^5 days.O(D)One flag per day.Handle events in order of end day. Give each one the earliest day in its range that is still free, scanning day by day. Events that end sooner have fewer choices, so serving them first and taking the earliest free day never blocks a better schedule.
- Sort events by end day (ties by start day).
- used = boolean array over days.
- For each event, scan d from start to end; at the first free d, mark it used, count++ and stop.
class Solution {
public int maxEvents(int[][] events) {
Arrays.sort(events, (a, b) -> a[1] != b[1] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
boolean[] used = new boolean[100002];
int count = 0;
for (int[] e : events) {
for (int d = e[0]; d <= e[1]; d++) {
if (!used[d]) {
used[d] = true;
count++;
break;
}
}
}
return count;
}
}class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
events.sort(key=lambda e: (e[1], e[0]))
used = [False] * 100002
count = 0
for s, e in events:
for d in range(s, e + 1):
if not used[d]:
used[d] = True
count += 1
break
return countclass 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] ? a[1] < b[1] : a[0] < b[0];
});
vector<bool> used(100002, false);
int count = 0;
for (auto& e : events) {
for (int d = e[0]; d <= e[1]; d++) {
if (!used[d]) {
used[d] = true;
count++;
break;
}
}
}
return count;
}
};function maxEvents(events) {
events.sort((a, b) => a[1] !== b[1] ? a[1] - b[1] : a[0] - b[0]);
const used = new Uint8Array(100002);
let count = 0;
for (const [s, e] of events) {
for (let d = s; d <= e; d++) {
if (!used[d]) {
used[d] = 1;
count++;
break;
}
}
}
return count;
}2Optimal (day sweep with a min-heap of end days)
O(n log n)Sorting plus one push and at most one pop per event; days with no open event are skipped.O(n)The heap can hold every event at once.Sweep the days in increasing order. When a day arrives, push the end day of every event that starts on it into a min-heap, drop ends that are already in the past, and attend the open event that ends soonest. When the heap is empty, jump straight to the next start day.
- Sort events by start day; i = 0, day = 0, count = 0.
- While i < n or the heap is not empty: if the heap is empty, set day to events[i] start.
- Push the end of every event with start == day (advance i).
- Pop ends smaller than day. If the heap is still non-empty, pop one, count++.
- day++ and repeat.
class Solution {
public int maxEvents(int[][] events) {
Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));
PriorityQueue<Integer> ends = new PriorityQueue<>();
int n = events.length, i = 0, day = 0, count = 0;
while (i < n || !ends.isEmpty()) {
if (ends.isEmpty()) day = events[i][0];
while (i < n && events[i][0] == day) ends.offer(events[i++][1]);
while (!ends.isEmpty() && ends.peek() < day) ends.poll();
if (!ends.isEmpty()) {
ends.poll();
count++;
}
day++;
}
return count;
}
}class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
events.sort(key=lambda e: e[0])
ends = []
n, i, day, count = len(events), 0, 0, 0
while i < n or ends:
if not ends:
day = events[i][0]
while i < n and events[i][0] == day:
heapq.heappush(ends, events[i][1])
i += 1
while ends and ends[0] < day:
heapq.heappop(ends)
if ends:
heapq.heappop(ends)
count += 1
day += 1
return countclass Solution {
public:
int maxEvents(vector<vector<int>>& events) {
sort(events.begin(), events.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
priority_queue<int, vector<int>, greater<int>> ends;
int n = events.size(), i = 0, day = 0, count = 0;
while (i < n || !ends.empty()) {
if (ends.empty()) day = events[i][0];
while (i < n && events[i][0] == day) ends.push(events[i++][1]);
while (!ends.empty() && ends.top() < day) ends.pop();
if (!ends.empty()) {
ends.pop();
count++;
}
day++;
}
return count;
}
};class MinHeap {
constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
size() { return this.a.length; }
isEmpty() { return this.a.length === 0; }
peek() { return this.a[0]; }
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.cmp(a[i], a[p]) >= 0) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length > 0) {
a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
function maxEvents(events) {
events.sort((a, b) => a[0] - b[0]);
const ends = new MinHeap();
const n = events.length;
let i = 0, day = 0, count = 0;
while (i < n || !ends.isEmpty()) {
if (ends.isEmpty()) day = events[i][0];
while (i < n && events[i][0] === day) ends.push(events[i++][1]);
while (!ends.isEmpty() && ends.peek() < day) ends.pop();
if (!ends.isEmpty()) {
ends.pop();
count++;
}
day++;
}
return count;
}Edge cases to test
- Many identical events squeezed into a short range
- A long event and a one-day event that both want the same day
- Gaps between events (days on which nothing is available)
Hints
Hint 1
On a given day, if several open events are available, which one is the most urgent to attend?
Hint 2
Pick the open event that ends soonest: it has the fewest days left to be used.
Hint 3
Sweep the days in order, add events as they open into a min-heap keyed by end day, and throw away the ones that have already ended.
FAQ
What is the best time complexity for Maximum Number of Events That Can Be Attended?
Optimal (day sweep with a min-heap of end days) runs in O(n log n) time and O(n) extra space. Sorting plus one push and at most one pop per event; days with no open event are skipped.
Which pattern does Maximum Number of Events That Can Be Attended use?
It is a heaps problem that uses the advanced pattern. Other problems with the same pattern: Find K Pairs with Smallest Sums, Find Median from Data Stream, Trapping Rain Water II.
Is there a brute force solution for Maximum Number of Events That Can Be Attended?
Yes. Brute force (earliest deadline, scan for a free day) takes O(n log n + n · D) time and O(D) space. Handle events in order of end day.
Which edge cases should I test for Maximum Number of Events That Can Be Attended?
Many identical events squeezed into a short range; A long event and a one-day event that both want the same day; Gaps between events (days on which nothing is available).