Maximum Events Attended

Problem

LeetCode 1353 — Maximum Number of Events That Can Be Attended

Given an array of events where events[i] = [startDay, endDay], you can attend one event per day on any single day within its [startDay, endDay] window. Return the maximum number of events you can attend.

Example

events = [[1,2],[2,3],[3,4]]  →  3
events = [[1,4],[4,4],[2,2],[3,4],[1,1]]  →  4

Approach — Greedy + Min-Heap

Key insight: on each day, among all events available (started but not yet expired), always attend the one that ends soonest. Attending a later-ending event today is never better — it has more remaining days to be attended later.

Algorithm:

1. Sort events by start day.
2. Sweep day by day from 1 to 100000.
3. On each day:
   • Add all events starting today into a min-heap keyed by end day.
   • Remove expired events from the heap (end day < today).
   • If heap is non-empty, pop the earliest-ending event and attend it.

Why greedy works

If you skip the earliest-ending available event today in favor of another, the skipped event either:

• Gets attended on a later day (fine, no loss), or
• Expires before you attend it (a loss you could have avoided).

Attending earliest-ending first never causes a loss — it’s the exchange argument that proves optimality.

Visual Walkthrough

Using the counterexample events = [[1,2], [1,3], [2,2]]:

Timeline view (each = is a day the event is available):

         Day 1   Day 2   Day 3
[1,2]  : [===]   [===]
[2,2]  :         [===]
[1,3]  : [===]   [===]   [===]

Sweep simulation:

Day 1:
  Add to heap (events starting day 1): end=2, end=3
  Heap: [ 2, 3 ]   ← min-heap, smallest on top
  No expiry.
  Pop 2 → attend [1,2]   ✓
  Heap: [ 3 ]

Day 2:
  Add to heap (events starting day 2): end=2
  Heap: [ 2, 3 ]
  No expiry (peek=2 >= today=2).
  Pop 2 → attend [2,2]   ✓
  Heap: [ 3 ]

Day 3:
  Nothing new starts.
  Heap: [ 3 ]
  No expiry (peek=3 >= today=3).
  Pop 3 → attend [1,3]   ✓
  Heap: []

Result: 3 ✓

Why the heap was the difference: on Day 2, both [2,2] (end=2) and [1,3] (end=3) were available. The heap surfaced end=2 first — the one about to expire — leaving [1,3] alive for Day 3. Sort-only would have picked [1,3] (earlier start), wasting Day 2’s opportunity to save a dying event.

Complexity

• Time: O(n log n) — sorting + each event pushed and popped from heap at most once
• Space: O(n) — heap holds at most n events

Solution

class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int attended = 0, i = 0, n = events.length;

        for (int day = 1; day <= 100000; day++) {
            while (i < n && events[i][0] == day)
                heap.offer(events[i++][1]);
            while (!heap.isEmpty() && heap.peek() < day)
                heap.poll();
            if (!heap.isEmpty()) {
                heap.poll();
                attended++;
            }
        }

        return attended;
    }
}

Why Sort-Only Greedy Fails (and Why the Heap is Necessary)

A natural first attempt is to sort by start day and greedily attend events in that order, jumping today forward as you go:

// Sort by start day, then end day
// For each event in order: skip if expired, jump today to startDay if needed, attend it

This feels right but fails when multiple events are available on the same day.

Counterexample: events = [[1,2], [1,3], [2,2]]

Sorted by (start, end): [[1,2], [1,3], [2,2]]

Returns 2. But the correct answer is 3: attend [1,2] day 1, [2,2] day 2, [1,3] day 3.

Why it went wrong: on day 2, both [1,3] and [2,2] were available. The sort-only approach picked [1,3] because it has an earlier start day. But [2,2] expires on day 2 — attending it now and saving [1,3] for day 3 would have been optimal.

The mental model: sorting by start day answers “which event became available first.” But the right question each day is “which available event will expire soonest?” — that is what the min-heap answers. An event with more days remaining can always be deferred; an event expiring today cannot.

Rule of thumb: whenever you need to repeatedly ask “best among currently available options” as options arrive over time, that’s a heap, not a sort.

Why It Teaches You Something

This problem looks like an interval scheduling problem but the twist — attending on any day within the window, not just the start — is what forces the greedy + heap approach.

The same pattern (sweep day by day, heap of active intervals, greedy pick) solves: