Compile Ready
Module 3 · Scheduling

Maximum Number of Events That Can Be Attended

MediumProblem 8 of 21 10 min read ~25 min to solve LeetCode
GreedyHeapSortingSchedulingIntervals
Asked atAmazonGoogleMicrosoftMetaBloomberg

Problem Statement

You are given an array events where events[i] = [startDay_i, endDay_i]. You may attend an event on any one day between its start and end day, inclusive, and you may attend at most one event per day.

Return the maximum number of events you can attend.

Input

An array events of inclusive day ranges.

Output

An integer: the maximum number of events that can be attended.

Constraints

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

Examples

Example 1

Input: 
events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: Attend the first event on day 1, the second on day 2, and the third on day 3.

Example 2

Input: 
events = [[1,2],[2,3],[3,4],[1,2]]
Output: 4
Explanation: Attend the two events ending on day 2 during days 1 and 2, then attend the remaining events on days 3 and 4.

Example 3

Input: 
events = [[1,1],[1,2],[1,2],[2,2]]
Output: 2
Explanation: Only days 1 and 2 are available across all events, so at most two events can be attended.

Learning Objectives

  • Use a day pointer to simulate only relevant calendar days.
  • Maintain available event deadlines in a min-heap.
  • Explain why attending the earliest-ending available event is the safe greedy choice.
  • Remove expired events before making each daily choice.

Intuition

Greedy Insight: On any day, several events may be available. Attend the event that ends earliest, because it has the least flexibility. Events with later end days can still survive to future days.

Sorting by start day is only how events enter the available set. The actual choice among available events is by earliest end day, so a min-heap of end days is the right data structure. When the heap is empty, the day pointer jumps to the next event start to avoid scanning empty calendar days.

The wrong sort key trap is to simply attend events in earliest-start order. An early-start event with a late deadline may be safely delayed, while a later-start event with an earlier deadline may expire immediately. Greedy scheduling is about the tightest deadline among currently available choices.

Common mistakes

  • ×Sorting by start day and attending in that order without considering end days.
  • ×Keeping expired events in the heap and accidentally attending them after their end day.
  • ×Incrementing the day one by one through long empty ranges instead of jumping to the next start when no events are available.
  • ×Choosing the event with the longest duration, which preserves the least urgent work and loses deadlines.

Algorithm Explanation

Greedy strategy Sort events by start day. Sweep a day pointer forward. For each day, add all events that have started to a min-heap keyed by end day, discard expired events, then attend the available event with the smallest end day.

Why it works All events in the heap can be attended today. The one ending earliest has the fewest remaining chances. Taking it today cannot hurt events with later end days because they remain available for at least as long.

Proof of correctness Fix a day d and suppose the greedy algorithm attends event g, the available event with the earliest end day. Consider an optimal schedule that agrees with greedy before day d but attends a different available event x on day d. Since g ends no later than x, event x is at least as flexible as g.

If the optimal schedule never attends g, replace x with g on day d and keep the same number of attended events. If the optimal schedule attends g on a later day d2, swap them: attend g on day d and attend x on day d2. This is feasible because x had already started by day d, so it has started by d2, and x ends no earlier than g, so it is still valid on d2. The optimal count is unchanged and now matches greedy on day d.

By repeating this exchange day by day, there exists an optimal schedule that makes every greedy choice. Therefore the greedy algorithm attends the maximum possible number of events.

Algorithm

  1. Sort events by start day.
  2. Maintain day, eventIndex, attended, and a min-heap of end days.
  3. If the heap is empty, jump day to the next event start.
  4. Add every event whose start day is at most day.
  5. Remove heap end days smaller than day because those events expired.
  6. If the heap is non-empty, attend the event with the smallest end day, increment attended, and move to the next day.
  7. Continue until all events are processed and the heap is empty.

Solutions

Solution: Sort by start day with earliest-deadline heap

The sorted array feeds newly available events into a min-heap. The heap always exposes the event whose deadline is most urgent, which is the event to attend on the current day.

Step-by-step

  1. Sort events by start day.
  2. If there are no currently available events, jump the day pointer to the next event start.
  3. Push all events that have started by the current day into the min-heap of end days.
  4. Pop expired end days that are smaller than the current day.
  5. Attend the event with the smallest end day, increment the answer, and advance one day.
Time

O(n log n)

Space

O(n)

Events are sorted once and each end day is pushed and popped at most once.

Java implementation

Loading…

Dry Run

Sample input

events = [[1,2],[2,3],[3,4],[1,2]]. Sorted by start day: [[1,2],[1,2],[2,3],[3,4]].

daynew events addedheap before attendattend end daycount after day
1[1,2], [1,2][2,2]21
2[2,3][2,3]22
3[3,4][3,4]33
4none[4]44

Each day chooses the available event with the earliest end day. The two events ending on day 2 are handled first, preserving later deadlines for days 3 and 4.

Interview Tips

Emphasise the two separate orderings: sort by start to know when events become available, then choose by end day to protect urgent deadlines. The exchange argument is the key: if an optimal schedule attends a later-ending available event today, swap in the earliest-ending event and the later-ending one remains at least as feasible afterward.

Likely follow-ups

  • How would the solution change if each event had a profit and you wanted maximum profit?
  • What if attending an event took multiple consecutive days?
  • How would you return the actual event indices selected?
  • Can you optimise when day values are extremely large but the number of events is modest?

Similar Problems

Meeting Rooms II
MediumAlso combines start-time ordering with an earliest-ending heap.
Task Scheduler
MediumAnother scheduling problem where the most constrained choice should be handled first.
Course Schedule III
HardSchedules courses by deadline while replacing expensive choices.
IPO
HardUses a heap over available choices after sorting by availability.
Maximum Profit in Job Scheduling
HardA weighted scheduling variant where greedy is no longer sufficient.

Key Takeaways

  • Sort by start day to discover events as they become available.
  • Among available events, attend the one with the earliest end day.
  • A min-heap of deadlines supports the greedy choice efficiently.
  • Jump the day pointer when no event is available to avoid wasted scanning.
Reusable template: Earliest-deadline scheduling: add all jobs available by the current time, discard expired jobs, and execute the available job with the smallest deadline.