Maximum Events Attended — Greedy and Min-Heap [LC 1353, Google]

Problem Statement#

Given events[i] = [startDay, endDay], you can attend at most one event per day. Return the maximum number of events you can attend.

Constraints:

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

Input:  events = [[1,2],[2,3],[3,4]]
Output: 3

Input:  events = [[1,2],[2,3],[3,4],[1,2]]
Output: 4

Why This Problem Matters#

LC 1353 is a classic greedy problem asked by Google and Amazon that demonstrates the "earliest deadline first" scheduling paradigm. The greedy insight — always attend the event that ends soonest among currently available events — minimises future conflicts and maximises total events attended.

The min-heap data structure is the natural tool for efficiently tracking which available events end soonest. This pattern (sort by start time, use a heap keyed by end time) appears in interval scheduling, task assignment, and meeting room problems.

The Core Insight#

Greedy invariant: on each day, attend the event with the earliest end date among all events that have started and not yet expired.

Algorithm:

1. Sort events by start day.
2. Iterate over days from min_start to max_end.
3. For each day: add all events that start on this day to a min-heap (keyed by end day). Remove expired events (end day < current day). Attend the earliest-ending available event (pop the heap).

The pointer i over the sorted events advances monotonically, so adding events to the heap is amortised O(1) per event across the entire loop.

Visual Dry Run#

events = [[1,2],[2,3],[3,4]] sorted: [[1,2],[2,3],[3,4]]

Result: 3

events = [[1,2],[1,2],[1,2],[1,2]] sorted: all the same

Result: 2

Solution (Optimal)#

import heapq
 
class Solution:
    def maxEvents(self, events: list[list[int]]) -> int:
        events.sort()  # sort by start day
        heap = []      # min-heap of end days
        n = len(events)
        i = 0          # pointer into sorted events
        ans = 0
 
        # Find day range
        day = events[0][0]
        max_day = max(e[1] for e in events)
 
        while i < n or heap:
            # If heap is empty, jump to the next event's start day
            if not heap:
                day = events[i][0]
 
            # Add all events that start on or before today
            while i < n and events[i][0] <= day:
                heapq.heappush(heap, events[i][1])  # push end day
                i += 1
 
            # Remove events that have already expired
            while heap and heap[0] < day:
                heapq.heappop(heap)
 
            # Attend the earliest-ending available event
            if heap:
                heapq.heappop(heap)  # attend this event today
                ans += 1
 
            day += 1
 
        return ans

var maxEvents = function(events) {
    events.sort((a, b) => a[0] - b[0]);  // sort by start day
 
    // Min-heap using an array (simplified — JavaScript lacks built-in heap)
    // For production, use a proper min-heap library or implement one
    class MinHeap {
        constructor() { this.data = []; }
        push(val) {
            this.data.push(val);
            this._bubbleUp(this.data.length - 1);
        }
        pop() {
            const top = this.data[0];
            const last = this.data.pop();
            if (this.data.length) { this.data[0] = last; this._sinkDown(0); }
            return top;
        }
        peek() { return this.data[0]; }
        get size() { return this.data.length; }
        _bubbleUp(i) {
            while (i > 0) {
                const p = (i - 1) >> 1;
                if (this.data[p] <= this.data[i]) break;
                [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
                i = p;
            }
        }
        _sinkDown(i) {
            const n = this.data.length;
            while (true) {
                let min = i, l = 2*i+1, r = 2*i+2;
                if (l < n && this.data[l] < this.data[min]) min = l;
                if (r < n && this.data[r] < this.data[min]) min = r;
                if (min === i) break;
                [this.data[min], this.data[i]] = [this.data[i], this.data[min]];
                i = min;
            }
        }
    }
 
    const heap = new MinHeap();
    const n = events.length;
    let i = 0, ans = 0;
    let day = events[0][0];
    const maxDay = Math.max(...events.map(e => e[1]));
 
    while (i < n || heap.size > 0) {
        if (heap.size === 0) day = events[i][0];
 
        while (i < n && events[i][0] <= day) {
            heap.push(events[i][1]);
            i++;
        }
 
        while (heap.size > 0 && heap.peek() < day) heap.pop();
 
        if (heap.size > 0) {
            heap.pop();
            ans++;
        }
 
        day++;
    }
 
    return ans;
};

Time: O(n log n) — sorting plus at most n heap operations, each O(log n) Space: O(n) — heap can hold all events in the worst case

Common Mistakes#

• Forgetting to remove expired events from the heap before attending — expired events have end < current_day.
• Not jumping the day pointer to the next event's start when the heap is empty — without this, the loop iterates over days with no available events.
• Sorting by end day instead of start day — the pointer needs to advance by start day to know which events become available.
• Using a max-heap instead of a min-heap — you want the earliest-ending event, not the latest.

Interview Tips#

• State the greedy invariant before coding: "always attend the event expiring soonest, because waiting longer can only lose opportunities."
• The day-jumping optimisation (skip to next event start when heap is empty) is necessary for correctness and efficiency.
• Mention the relationship to interval scheduling maximisation — this is the "weighted" version with weight 1 per event.

Follow-up Questions#

• LC 1751 (Maximum Events Attended II): Each event has a value; attend at most k events to maximise total value. Requires DP + binary search.
• Meeting Rooms II (LC 253): How many rooms needed? Similar min-heap approach on end times.
• Task Scheduler (LC 621): Schedule tasks with cooldowns — same greedy spirit.
• What if each event takes multiple days? This becomes an interval scheduling problem with weight equal to event duration.

Key Takeaways#

• LC 1353 uses the earliest-deadline-first greedy: always attend the available event with the smallest end day to minimise future conflicts.
• Sort events by start day, then use a min-heap of end days to track currently available events efficiently.
• The pointer i advances monotonically, so adding events to the heap is O(1) amortised across all days.
• Always remove expired events (end day < current day) from the heap before deciding whether to attend anything on the current day.
• Jump the day pointer to the next event start when the heap is empty — without this optimisation, the solution becomes O(max_day * log n).
• Google and Amazon ask this to test interval scheduling knowledge and min-heap usage in greedy algorithms.
• This pattern — sort by start, heap on end — appears in Meeting Rooms II (LC 253) and Maximum Events Attended II (LC 1751).