Maximum Number of Events That Can Be Attended

Medium
964.

Maximum Number of Events That Can Be Attended

MediumArrayGreedySortingHeap (Priority Queue)AmazonGoogleAdobe

Maximum Number of Events That Can Be Attended is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Adobe interviews.

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
4

Example 3

Input
events = [[1,1],[1,1],[1,1]]
Output
1
Explanation
All three need the same single day.

Constraints

  • 1 <= events.length <= 10^5
  • events[i].length == 2
  • 1 <= startDay <= endDay <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} events
 * @return {number}
 */
var maxEvents = function(events) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Number of Events That Can Be Attended — Solution

Maximum Number of Events That Can Be Attended solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Number of Events That Can Be Attended is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Greedy, 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: 4

Example 3

Input: events = [[1,1],[1,1],[1,1]]
Output: 1
Explanation: All three need the same single day.

Constraints

  • 1 <= events.length <= 10^5
  • events[i].length == 2
  • 1 <= startDay <= endDay <= 10^5

Hints for Maximum Number of Events That Can Be Attended

  1. Hint 1

    Walk the calendar day by day rather than event by event.

  2. Hint 2

    On each day, which of the events currently available should you attend?

  3. Hint 3

    The one that ends soonest — a min-heap of end days gives it in O(log n).

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

  1. Sort the events by start day.
  2. For day 1 … maxEnd: push every event starting today onto the heap.
  3. Discard heap entries whose end day is before today.
  4. 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 count

Java

public static int maxEvents(int[][] events) {
    int[][] sorted = events.clone();
    Arrays.sort(sorted, (a, b) -> a[0] - b[0]);
    int maxDay = 0;
    for (int[] e : events) maxDay = Math.max(maxDay, e[1]);
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    int at = 0, count = 0;
    for (int day = 1; day <= maxDay; day++) {
        while (at < sorted.length && sorted[at][0] == day) heap.add(sorted[at++][1]);
        while (!heap.isEmpty() && heap.peek() < day) heap.poll();
        if (!heap.isEmpty()) {
            heap.poll();
            count++;
        }
    }
    return count;
}

C++

int maxEvents(vector<vector<int>>& events) {
    vector<vector<int>> sorted = events;
    sort(sorted.begin(), sorted.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
    int maxDay = 0;
    for (auto& e : events) maxDay = max(maxDay, e[1]);
    priority_queue<int, vector<int>, greater<int>> heap;
    size_t at = 0;
    int count = 0;
    for (int day = 1; day <= maxDay; day++) {
        while (at < sorted.size() && sorted[at][0] == day) heap.push(sorted[at++][1]);
        while (!heap.empty() && heap.top() < day) heap.pop();
        if (!heap.empty()) {
            heap.pop();
            count++;
        }
    }
    return count;
}

JavaScript

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms