LeetCode 1353 - Maximum Number of Events That Can Be Attended

LeetCode Problem 1353

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives us a list of events, where each event is represented as a pair [startDay, endDay]. An event is available to attend on any single day within that inclusive range. The goal is to attend as many events as possible, with the restriction that only one event can be attended per day.

In other words, each event occupies a flexible interval rather than a fixed time slot. We are free to choose exactly one day for each event, as long as that day lies between its start and end days. Since multiple events may overlap on the same days, we must decide carefully which event to attend on each day to maximize the total count.

For example, if we have an event [1, 3], we could attend it on day 1, day 2, or day 3. Once we choose a day for that event, that day cannot be used for another event.

The input size is large:

• Up to 10^5 events
• Days can also go up to 10^5

These constraints immediately rule out highly inefficient approaches. Any algorithm with quadratic complexity, such as checking every event against every day repeatedly, will be too slow.

The problem guarantees that:

• Every event has exactly two integers
• startDay <= endDay
• All values are positive

Several edge cases are important to recognize early:

• Multiple events may have identical ranges
• Many events may overlap heavily on the same days
• Some events may last only one day, such as [5, 5]
• Events may start far apart, creating gaps in the calendar
• Large numbers of events may all end on the same day

A naive strategy can easily fail if it greedily attends long-duration events too early and blocks shorter, urgent events later.

Approaches

Brute Force Approach

A brute-force strategy would try to process events one by one and assign each event to the earliest available day in its interval.

One possible implementation is:

1. Sort events by start day.
2. For each event, scan every day from startDay to endDay.
3. If an unused day is found, attend the event on that day.
4. Mark that day as occupied.

This works because every event attempts to claim a valid free day within its range.

However, this approach becomes too slow when intervals are large. In the worst case:

• There are 10^5 events
• Each event spans 10^5 days

That leads to potentially O(N * D) work, which can approach 10^10 operations.

This is far beyond acceptable limits.

Key Insight Behind the Optimal Solution

The critical observation is that when multiple events are available on a given day, we should attend the event that ends earliest.

Why?

Because events with earlier ending days are more urgent. If we postpone them, they may expire and become impossible to attend later. Events with later ending days are more flexible and can often be scheduled in the future.

This naturally leads to a greedy strategy:

• Process days in chronological order
• Add all events that have started by the current day
• Among available events, always attend the one with the smallest end day

To efficiently retrieve the event with the earliest ending day, we use a min-heap.

The heap stores ending days of currently available events.

This combination of sorting and a priority queue allows us to always make the locally optimal decision while maintaining efficiency.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N × D)	O(D)	Scans days repeatedly for each event
Optimal	O(N log N)	O(N)	Uses sorting and a min-heap to greedily attend earliest-ending events

Algorithm Walkthrough

Optimal Greedy + Min-Heap Algorithm

1. Sort all events by their start day.

Processing events chronologically allows us to know exactly when events become available. Once sorted, we can iterate through days and progressively add events into consideration. 2. Maintain a min-heap containing ending days of currently available events.

The heap represents all events that:

• Have already started
• Have not yet expired
• Have not been attended

The smallest value in the heap corresponds to the event that ends earliest. 3. Iterate day by day.

We simulate the calendar from the earliest relevant day onward. 4. Add all events whose start day equals the current day.

These events become available to attend starting today, so we push their end days into the heap. 5. Remove expired events from the heap.

Any event whose end day is less than the current day can no longer be attended. Those events must be discarded. 6. Attend one event if possible.

If the heap is not empty, pop the smallest end day from the heap.

This corresponds to attending the event that expires soonest.

Increment the answer count. 7. Continue until all events are processed and the heap becomes empty.

At that point, no more events remain that can be attended.

Why it works

The greedy choice is always optimal because attending the event with the earliest ending day preserves maximum flexibility for future days.

Suppose we instead attended an event that ends later while skipping one that ends sooner. The later-ending event could still potentially be attended on a future day, but the earlier-ending event may expire permanently. Therefore, prioritizing earlier deadlines can never reduce the optimal answer.

This is a classic interval scheduling greedy argument.

Python Solution

from typing import List
import heapq

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        events.sort()

        min_heap = []
        event_index = 0
        attended = 0

        max_day = max(end for _, end in events)

        for day in range(1, max_day + 1):

            while event_index < len(events) and events[event_index][0] == day:
                heapq.heappush(min_heap, events[event_index][1])
                event_index += 1

            while min_heap and min_heap[0] < day:
                heapq.heappop(min_heap)

            if min_heap:
                heapq.heappop(min_heap)
                attended += 1

        return attended

The implementation begins by sorting the events by start day. This ensures that events are introduced into the heap exactly when they become available.

The min_heap stores end days of active events. Python's heapq module provides an efficient min-priority queue implementation.

The variable event_index tracks which events have already been inserted into the heap. As the current day advances, newly available events are pushed into the heap.

Before attending an event on a given day, expired events are removed. Any event whose ending day is earlier than the current day is no longer valid.

If at least one valid event remains, the algorithm attends the event with the smallest end day by popping from the heap.

The count of attended events is accumulated in attended.

Go Solution

package main

import (
	"container/heap"
	"sort"
)

type MinHeap []int

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	value := old[n-1]
	*h = old[:n-1]
	return value
}

func maxEvents(events [][]int) int {
	sort.Slice(events, func(i, j int) bool {
		return events[i][0] < events[j][0]
	})

	maxDay := 0
	for _, event := range events {
		if event[1] > maxDay {
			maxDay = event[1]
		}
	}

	minHeap := &MinHeap{}
	heap.Init(minHeap)

	eventIndex := 0
	attended := 0

	for day := 1; day <= maxDay; day++ {

		for eventIndex < len(events) && events[eventIndex][0] == day {
			heap.Push(minHeap, events[eventIndex][1])
			eventIndex++
		}

		for minHeap.Len() > 0 && (*minHeap)[0] < day {
			heap.Pop(minHeap)
		}

		if minHeap.Len() > 0 {
			heap.Pop(minHeap)
			attended++
		}
	}

	return attended
}

The Go implementation follows the same algorithmic structure as the Python version. The primary difference is that Go does not provide a built-in heap abstraction for integers, so we implement the heap.Interface.

The heap stores event end days exactly as in Python. Since all constraints fit comfortably within Go's standard int type, integer overflow is not a concern here.

Go slices are dynamically sized, making them a natural backing structure for the heap implementation.

Worked Examples

Example 1

Input:

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

Sorted events:

[[1,2],[2,3],[3,4]]

Day	Events Added	Heap Before Attend	Event Attended	Heap After Attend	Total
1	2	[2]	ends at 2	[]	1
2	3	[3]	ends at 3	[]	2
3	4	[4]	ends at 4	[]	3

Final answer:

3

Example 2

Input:

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

Sorted events:

[[1,2],[1,2],[2,3],[3,4]]

Day	Events Added	Heap Before Attend	Event Attended	Heap After Attend	Total
1	2, 2	[2,2]	one ending at 2	[2]	1
2	3	[2,3]	one ending at 2	[3]	2
3	4	[3,4]	one ending at 3	[4]	3
4	none	[4]	one ending at 4	[]	4

Final answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N log N)	Sorting costs O(N log N), heap operations across all events also total O(N log N)
Space	O(N)	The heap may contain up to N events simultaneously

The sorting step dominates the initial preprocessing cost. Each event is inserted into and removed from the heap at most once. Since heap operations cost O(log N), the total heap work is also O(N log N).

The heap stores active events, which in the worst case may include all events simultaneously.

Test Cases

from typing import List

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        import heapq

        events.sort()

        min_heap = []
        event_index = 0
        attended = 0

        max_day = max(end for _, end in events)

        for day in range(1, max_day + 1):

            while event_index < len(events) and events[event_index][0] == day:
                heapq.heappush(min_heap, events[event_index][1])
                event_index += 1

            while min_heap and min_heap[0] < day:
                heapq.heappop(min_heap)

            if min_heap:
                heapq.heappop(min_heap)
                attended += 1

        return attended

solution = Solution()

assert solution.maxEvents([[1,2],[2,3],[3,4]]) == 3
# basic non-overlapping chain

assert solution.maxEvents([[1,2],[2,3],[3,4],[1,2]]) == 4
# overlapping intervals with optimal scheduling

assert solution.maxEvents([[1,1],[1,1],[1,1]]) == 1
# all events occur on same single day

assert solution.maxEvents([[1,10]]) == 1
# single event spanning many days

assert solution.maxEvents([[1,2],[1,2],[1,2],[1,2]]) == 2
# multiple identical overlapping events

assert solution.maxEvents([[1,4],[4,4],[2,2],[3,4],[1,1]]) == 4
# mixed interval lengths

assert solution.maxEvents([[5,5],[1,2],[1,2],[2,3],[3,4]]) == 5
# includes isolated future event

assert solution.maxEvents([[1,100000]]) == 1
# maximum day range

assert solution.maxEvents([[1,3],[1,3],[1,3],[3,4]]) == 4
# heap prioritization required

assert solution.maxEvents([[2,2],[2,2],[2,2],[1,2]]) == 2
# many events expiring simultaneously

Test	Why
[[1,2],[2,3],[3,4]]	Basic sequential scheduling
[[1,2],[2,3],[3,4],[1,2]]	Standard overlapping example
[[1,1],[1,1],[1,1]]	Single-day collision handling
[[1,10]]	Single long-duration event
[[1,2],[1,2],[1,2],[1,2]]	Heavy overlap with limited attendance
[[1,4],[4,4],[2,2],[3,4],[1,1]]	Mixed interval sizes
[[5,5],[1,2],[1,2],[2,3],[3,4]]	Gaps between event groups
[[1,100000]]	Maximum day boundary
[[1,3],[1,3],[1,3],[3,4]]	Greedy earliest-end validation
[[2,2],[2,2],[2,2],[1,2]]	Simultaneous expiration handling

Edge Cases

Multiple events with identical ranges

A common source of bugs occurs when many events share exactly the same start and end days. For example:

[[1,2],[1,2],[1,2]]

Only two events can actually be attended because there are only two available days. A naive implementation may accidentally overcount if it does not correctly mark days as used.

The heap-based solution handles this naturally by allowing only one event to be popped and attended per day.

Events that last only one day

Events such as [5,5] are extremely restrictive because they can only be attended on a single exact day.

If the algorithm postpones them even briefly, they immediately expire.

The greedy strategy prioritizes earliest ending days, which ensures that these single-day events are attended before more flexible events whenever necessary.

Large overlapping intervals

Consider many events like:

[[1,100000],[1,100000],[1,100000]]

A brute-force approach may waste enormous time scanning days repeatedly.

The heap solution avoids rescanning intervals entirely. Each event is inserted once and removed once, maintaining efficient O(N log N) performance even for maximum constraints.