Maximum Number of Events That Can Be Attended — Medium Problem & Solution
events[i] = [startDay, endDay] means event i runs from startDay to endDay inclusive.
- Difficulty: Medium
- Topics: Arrays, Greedy, Sorting, Heap
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
events[i] = [startDay, endDay] means event i runs from startDay to endDay inclusive. You may attend one event per day, and you may attend any single day of an event rather than the whole of it.
Return the maximum number of events you can attend.
Example 1
Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: Attend one on day 1, the next on day 2, the last on day 3.Example 2
Input: events = [[1,2],[2,3],[3,4],[1,2]]
Output: 4Example 3
Input: events = [[1,1],[1,1],[1,1]]
Output: 1
Explanation: All three need the same single day.Constraints
1 <= events.length <= 10^5events[i].length == 21 <= startDay <= endDay <= 10^5
How to solve Maximum Number of Events That Can Be Attended
Sweep the days in order. Each day, add every event that starts today to a min-heap keyed on end day, drop the ones that have already expired, and attend the one that ends soonest.
Approach
- Sort the events by start day.
- For day
1 … maxEnd: push every event starting today onto the heap. - Discard heap entries whose end day is before today.
- If the heap is non-empty, pop one — that event is attended — and count it.
Why it works
Attending the soonest-ending available event is optimal by an exchange argument: any schedule that attends a later-ending one today can swap the two without losing anything, since the later-ending event stays available longer. Expired entries are dropped lazily at the top of the heap rather than searched for, which keeps the sweep near-linear.
Complexity
- Time —
O(maxDay + n log n) - Space —
O(n)
Pitfalls
- Sorting by end day and greedily taking events whole is a different problem.
- Expired events must be discarded before the day's pick, not after.
- Both ends are inclusive: an event
[3, 3]is attendable exactly on day 3.
Reference solution
Python
from typing import List
import heapq
def maxEvents(events: List[List[int]]) -> int:
ordered = sorted(events, key=lambda e: e[0])
max_day = max(e[1] for e in events)
heap = []
at = 0
count = 0
for day in range(1, max_day + 1):
while at < len(ordered) and ordered[at][0] == day:
heapq.heappush(heap, ordered[at][1])
at += 1
while heap and heap[0] < day:
heapq.heappop(heap)
if heap:
heapq.heappop(heap)
count += 1
return countJavaScript
var maxEvents = function(events) {
var sorted = events.slice();
sorted.sort(function(a, b) { return a[0] - b[0]; });
var maxDay = 0, i;
for (i = 0; i < events.length; i++) if (events[i][1] > maxDay) maxDay = events[i][1];
var heap = [];
var push = function(v) {
heap.push(v);
var j = heap.length - 1;
while (j > 0) {
var p = (j - 1) >> 1;
if (heap[p] <= heap[j]) break;
var t = heap[p]; heap[p] = heap[j]; heap[j] = t;
j = p;
}
};
var pop = function() {
var last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
var j = 0;
for (;;) {
var l = 2 * j + 1, r = l + 1, s = j;
if (l < heap.length && heap[l] < heap[s]) s = l;
if (r < heap.length && heap[r] < heap[s]) s = r;
if (s === j) break;
var t = heap[s]; heap[s] = heap[j]; heap[j] = t;
j = s;
}
}
};
var at = 0, count = 0;
for (var day = 1; day <= maxDay; day++) {
while (at < sorted.length && sorted[at][0] === day) { push(sorted[at][1]); at++; }
while (heap.length > 0 && heap[0] < day) pop();
if (heap.length > 0) { pop(); count++; }
}
return count;
};Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.