Maximum Number of Events That Can Be Attended
Description
Each event has a start day and an end day, and you can attend it on any one day from the start to the end, both included. You can attend at most one event per day. Return the largest number of events you can attend.
Examples
Example 1
Input: events = [[1, 2], [2, 3], [3, 4]]
Output: 3
Explanation: Attend the first on day 1, the second on day 2 and the third on day 3.
Example 2
Input: events = [[1, 2], [2, 3], [3, 4], [1, 2]]
Output: 4
Explanation: Days 1 to 4 each get one event: the two [1, 2] events take days 1 and 2.
Constraints
- 1 ≤ events.length ≤ 10^5
- 1 ≤ startDay ≤ endDay ≤ 10^5
Editorial
Approach 1 - The Earliest Free Day, Events by End
Intuition
Take the events in order of end day, so the one with the least room comes first, and give each its earliest free day in its range. That never hurts a later event: a later one ends no sooner, so any day this one could have used, it could too, and taking the earliest leaves the later days open.
Finding the earliest free day is the slow part. Walking forward one day at a time passes every day already taken: with 100,000 events that all span every day, that's about 5 billion steps, and our tests include that case, where the walk runs out of time. So keep a pointer for each day to the first day from it that might be free. Taking day d points it at d + 1, and every walk shortens the pointers it followed, so the next walk over the same days is quick.
Step-by-Step Explanation
Let's take events = [[1, 3], [1, 1], [2, 4], [2, 2], [3, 4]]:
- [1, 1] ends on day 1, and day 1, its first, is free. It takes it.
- [2, 2] ends on day 2, and day 2, its first, is free. It takes it.
- [1, 3] ends on day 3. Its earliest free day from 1 on is day 3, so it takes day 3.
- [2, 4] ends on day 4. Its earliest free day from 2 on is day 4, so it takes day 4.
- [3, 4] ends on day 4, and days 3 to 4 are all taken. It misses out.
- 4 events attended. The shaded columns are the days in use.
Each Event's Earliest Free Day — Events sorted by end day; each bar covers its days. The indigo one is choosing, green ones got a day, and the shaded columns are the days in use.
Algorithm
- Sort the events by end day.
- Point every day at itself.
- For each event, follow the pointers from its start day to the first free day, shortening them on the way. If that day is no later than the event's end, take it: count the event and point the day at the next one.
Code
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]; }); // by end day
int last = events.back()[1];
vector<int> nxt(last + 2); // nxt[d]: the first day from d on that might be free
iota(nxt.begin(), nxt.end(), 0);
int attended = 0;
for (const auto& e : events) {
int day = e[0];
while (nxt[day] != day) day = nxt[day]; // follow the pointers past taken days
for (int d = e[0]; nxt[d] != day; ) { int up = nxt[d]; nxt[d] = day; d = up; } // and shorten them
if (day <= e[1]) { // its earliest free day is inside its range: take it
attended++;
nxt[day] = day + 1; // that day is gone
}
}
return attended;
}
};
class Solution:
def maxEvents(self, events: list[list[int]]) -> int:
events.sort(key=lambda e: e[1]) # by end day
nxt = list(range(events[-1][1] + 2)) # nxt[d]: the first day from d on that might be free
attended = 0
for start, end in events:
day = start
while nxt[day] != day: # follow the pointers past taken days
day = nxt[day]
d = start
while nxt[d] != day: # and shorten them, so the next walk is quick
nxt[d], d = day, nxt[d]
if day <= end: # its earliest free day is inside its range: take it
attended += 1
nxt[day] = day + 1 # that day is gone
return attended
class Solution {
public int maxEvents(int[][] events) {
Arrays.sort(events, (a, b) -> Integer.compare(a[1], b[1])); // by end day
int[] nxt = new int[events[events.length - 1][1] + 2]; // the first day from d on that might be free
for (int d = 0; d < nxt.length; d++) nxt[d] = d;
int attended = 0;
for (int[] e : events) {
int day = e[0];
while (nxt[day] != day) day = nxt[day]; // follow the pointers past taken days
for (int d = e[0]; nxt[d] != day; ) { int up = nxt[d]; nxt[d] = day; d = up; } // and shorten them
if (day <= e[1]) { // its earliest free day is inside its range: take it
attended++;
nxt[day] = day + 1; // that day is gone
}
}
return attended;
}
}
var maxEvents = function(events) {
events.sort((a, b) => a[1] - b[1]); // by end day
const nxt = Array.from({ length: events[events.length - 1][1] + 2 }, (_, d) => d); // first maybe-free day
let attended = 0;
for (const [start, end] of events) {
let day = start;
while (nxt[day] !== day) day = nxt[day]; // follow the pointers past taken days
for (let d = start; nxt[d] !== day; ) { const up = nxt[d]; nxt[d] = day; d = up; } // and shorten them
if (day <= end) { // its earliest free day is inside its range: take it
attended++;
nxt[day] = day + 1; // that day is gone
}
}
return attended;
};
Complexity Analysis
Time Complexity: O(n log n + D)
The sort, then walks that the shortened pointers keep close to constant time each.
Space Complexity: O(D)
One pointer per day.
Why Look Day by Day Instead
Both ways are fast, and both rest on the same rule: the event with the fewest days left goes first. The first needs the pointer trick to stay fast. Walking the days instead gets the same choice from a min-heap of end days, which is the version most interviewers expect.
Approach 2 - Day by Day with a Min-Heap
Intuition
Go through the days in order. On each day the events that start join the open ones; any open event that already ended is thrown out; and the open event that ends soonest gets today, because it has the fewest days left to be attended on. If nothing is open, jump straight to the next start day.
Step-by-Step Explanation
Let's take the same events:
- Day 1. [1, 1] and [1, 3] start today. Attend [1, 1], the open event that ends soonest.
- Day 2. [2, 2] and [2, 4] start today. Attend [2, 2], the open event that ends soonest.
- Day 3. [3, 4] starts today. Attend [1, 3], the open event that ends soonest.
- Day 4. Attend [2, 4], the open event that ends soonest.
- 4 events attended. [3, 4] missed out.
One Event a Day — Each bar covers an event's days; the amber line is today. Amber events are open, the indigo one gets today, green ones were attended, and dashed ones ran out of days.
Algorithm
- Sort the events by start day.
- Each day, push the end days of the events that start, pop the end days already past, and if anything is left, pop the smallest and count it.
- When nothing is open, jump to the next start day.
Code
class Solution {
public:
int maxEvents(vector<vector<int>>& events) {
sort(events.begin(), events.end()); // by start day
priority_queue<int, vector<int>, greater<int>> openEnds; // end days of events that have started
int n = events.size(), i = 0, day = 0, attended = 0;
while (i < n || !openEnds.empty()) {
if (openEnds.empty()) day = max(day, events[i][0]); // nothing is open: jump to the next start
while (i < n && events[i][0] <= day) openEnds.push(events[i++][1]);
while (!openEnds.empty() && openEnds.top() < day) openEnds.pop(); // ended before today
if (!openEnds.empty()) {
openEnds.pop(); // attend the one that ends soonest
attended++;
day++;
}
}
return attended;
}
};
import heapq
class Solution:
def maxEvents(self, events: list[list[int]]) -> int:
events.sort() # by start day
open_ends, i, n = [], 0, len(events) # a min-heap of the end days of events that have started
day = attended = 0
while i < n or open_ends:
if not open_ends:
day = max(day, events[i][0]) # nothing is open: jump to the next start
while i < n and events[i][0] <= day:
heapq.heappush(open_ends, events[i][1])
i += 1
while open_ends and open_ends[0] < day:
heapq.heappop(open_ends) # it ended before today: too late for it
if open_ends:
heapq.heappop(open_ends) # attend the one that ends soonest
attended += 1
day += 1
return attended
class Solution {
public int maxEvents(int[][] events) {
Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0])); // by start day
PriorityQueue<Integer> openEnds = new PriorityQueue<>(); // end days of events that have started
int n = events.length, i = 0, day = 0, attended = 0;
while (i < n || !openEnds.isEmpty()) {
if (openEnds.isEmpty()) day = Math.max(day, events[i][0]); // nothing is open: jump ahead
while (i < n && events[i][0] <= day) openEnds.add(events[i++][1]);
while (!openEnds.isEmpty() && openEnds.peek() < day) openEnds.poll(); // ended before today
if (!openEnds.isEmpty()) {
openEnds.poll(); // attend the one that ends soonest
attended++;
day++;
}
}
return attended;
}
}
var maxEvents = function(events) {
events.sort((a, b) => a[0] - b[0]); // by start day
const heap = []; // a min-heap of the end days of events that have started
const push = (x) => {
heap.push(x);
for (let k = heap.length - 1; k > 0; ) {
const p = (k - 1) >> 1;
if (heap[p] <= heap[k]) break;
[heap[p], heap[k]] = [heap[k], heap[p]];
k = p;
}
};
const pop = () => {
const top = heap[0], last = heap.pop();
if (heap.length) {
heap[0] = last;
for (let k = 0; ; ) {
const l = 2 * k + 1, r = l + 1;
let m = k;
if (l < heap.length && heap[l] < heap[m]) m = l;
if (r < heap.length && heap[r] < heap[m]) m = r;
if (m === k) break;
[heap[m], heap[k]] = [heap[k], heap[m]];
k = m;
}
}
return top;
};
const n = events.length;
let i = 0, day = 0, attended = 0;
while (i < n || heap.length) {
if (!heap.length) day = Math.max(day, events[i][0]); // nothing is open: jump to the next start
while (i < n && events[i][0] <= day) push(events[i++][1]);
while (heap.length && heap[0] < day) pop(); // it ended before today: too late for it
if (heap.length) {
pop(); // attend the one that ends soonest
attended++;
day++;
}
}
return attended;
};
Complexity Analysis
Time Complexity: O(n log n)
The sort, and each event enters and leaves the heap once. Empty days are skipped.
Space Complexity: O(n)
The heap.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Attending in start order. for start, end in sorted(events):
On events = [[1, 1], [1, 3], [2, 2]] it returns 2; the answer is 3. A long event that starts early can take a day a one-day event needed. On each day, the event with the fewest days left should go first, not the one that started first.
Never dropping ended events. heapq.heappop(open_ends)
On events = [[1, 1], [1, 1], [2, 3]] it returns 3; the answer is 2. An event that ended yesterday is still in the heap, and popping it counts an event on a day it isn't on. Throw out every end day before today first.
Only trying the start day. if start not in taken:
On events = [[1, 2], [1, 2]] it returns 1; the answer is 2. An event can go on any day of its range. Giving up when its first day is taken loses events that had later days free.
Where This Pattern Is Taught
Choosing intervals by their ends, and this problem's day-by-day heap, are taught in Interval Scheduling: Sort by End Time.