Maximum Number of Events That Can Be Attended

medium array greedy heap sorting

Problem

You are given an array of events where each event is a pair [start, end] meaning it runs from day start to day end inclusive. You may attend exactly one event on any single day, and you may attend an event on any one day within its [start, end] range. Return the maximum number of distinct events you can attend.

Inputevents = [[1, 2], [2, 3], [3, 4]]

Output3

Attend event [1,2] on day 1, [2,3] on day 2, and [3,4] on day 3 — all three fit.

events (pairs like 1-2, 2-3, 3-4)

import heapq

def max_events(events):
    events.sort()
    heap = []
    i, n, day, count = 0, len(events), 0, 0
    while i < n or heap:
        if not heap:
            day = events[i][0]
        while i < n and events[i][0] == day:
            heapq.heappush(heap, events[i][1])
            i += 1
        heapq.heappop(heap)
        count += 1
        day += 1
        while heap and heap[0] < day:
            heapq.heappop(heap)
    return count

function maxEvents(events) {
  events.sort((a, b) => a[0] - b[0]);
  const heap = [];
  const push = (x) => { heap.push(x); heap.sort((a, b) => a - b); };
  let i = 0, n = events.length, day = 0, count = 0;
  while (i < n || heap.length) {
    if (!heap.length) day = events[i][0];
    while (i < n && events[i][0] === day) push(events[i++][1]);
    heap.shift();
    count++;
    day++;
    while (heap.length && heap[0] < day) heap.shift();
  }
  return count;
}

class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int i = 0, n = events.length, day = 0, count = 0;
        while (i < n || !heap.isEmpty()) {
            if (heap.isEmpty()) day = events[i][0];
            while (i < n && events[i][0] == day) heap.add(events[i++][1]);
            heap.poll();
            count++;
            day++;
            while (!heap.isEmpty() && heap.peek() < day) heap.poll();
        }
        return count;
    }
}

int maxEvents(vector<vector<int>>& events) {
    sort(events.begin(), events.end());
    priority_queue<int, vector<int>, greater<int>> heap;
    int i = 0, n = events.size(), day = 0, count = 0;
    while (i < n || !heap.empty()) {
        if (heap.empty()) day = events[i][0];
        while (i < n && events[i][0] == day) heap.push(events[i++][1]);
        heap.pop();
        count++;
        day++;
        while (!heap.empty() && heap.top() < day) heap.pop();
    }
    return count;
}

Explanation

Each event gives us a window of days [start, end], and we can only pick one event per day. The goal is to squeeze in as many events as possible, so the order in which we commit to events matters.

The greedy insight is this: on any given day, among all the events that are currently available (already started, not yet expired), you should attend the one that ends soonest. Why? An event with a later end day is more flexible — it still has days left to be attended later. The event about to expire has the fewest chances remaining, so grab it now.

To do this efficiently we sort events by their start day and sweep through the calendar one day at a time. A min-heap keyed on end day holds every event that has started but is still attendable. Each day we: push all events that start today into the heap, drop the soonest-ending one (attend it), advance the day, then discard any events at the top of the heap whose end day has already passed.

Walkthrough on events = [[1,2], [2,3], [3,4]]. Day 1: push end=2 into the heap, attend it (count 1). Day 2: push end=3, attend it (count 2). Day 3: push end=4, attend it (count 3). All three events fit, so the answer is 3.

Sorting and the heap together keep this fast even when events overlap heavily, because we never re-scan the whole list — each event enters and leaves the heap exactly once.

Time: O(n log n) Space: O(n)