Is Maximum Number of Events That Can Be Attended easy or hard?

Maximum Number of Events That Can Be Attended is rated Medium difficulty on LeetCode. The challenge comes from recognizing the greedy scheduling pattern and combining sorting with a priority queue to efficiently select the next event.

Maximum Number of Events That Can Be Attended Python/Java solution

In Python, the typical solution uses the heapq module to maintain a min-heap of end days while iterating through sorted events. Java implementations use PriorityQueue for the same purpose. Both follow the same greedy idea: always attend the event that ends earliest among currently available events.

How to solve Maximum Number of Events That Can Be Attended in O(n)?

A strict O(n) solution is not practical because events must be processed in chronological order and prioritized by ending time. Sorting and heap operations are required, leading to an optimal complexity of O(n log n). Attempts to remove sorting generally fail when event ranges overlap heavily.

What is the best approach for Maximum Number of Events That Can Be Attended?

The best approach is a greedy algorithm combined with a min-heap (priority queue). Sort events by start day, add active events to a heap ordered by end day, and attend the event that finishes earliest each day. This strategy avoids losing short-duration events and runs in O(n log n) time.

Is Maximum Number of Events That Can Be Attended asked at Google/Amazon/Meta?

This problem represents a classic interval scheduling pattern frequently used in technical interviews. Variations of event scheduling with greedy and priority queue logic have appeared in interviews at companies such as Google, Amazon, and Meta.

What data structure is used in Maximum Number of Events That Can Be Attended?

The optimal solution uses a min-heap (priority queue) to track active events by their end day. Some implementations also use ordered sets or balanced binary search trees to track available days when applying a greedy scheduling strategy.

What is the time complexity of Maximum Number of Events That Can Be Attended?

The optimal solution runs in O(n log n) time. Sorting the events takes O(n log n), and each event is inserted and removed from the min-heap at most once, which adds another O(n log n). Space complexity is O(n) due to the heap storing active events.

Description Hints 2 Solution Video 11:50

1353. Maximum Number of Events That Can Be Attended

Medium38.9% acceptance16 companies

You are given an array of events where events[i] = [startDay_i, endDay_i]. Every event i starts at startDay_iand ends at endDay_i.

You can attend an event i at any day d where startTime_i <= d <= endTime_i. You can only attend one event at any time d.

Return the maximum number of events you can attend.

Example 1:

Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.

Example 2:

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

Constraints:

1 <= events.length <= 10⁵
events[i].length == 2
1 <= startDay_i <= endDay_i <= 10⁵

Asked at 16 companies

Gopuff Visa PayPal Snowflake Microsoft Uber Oracle NVIDIA Expedia

Google Amazon Zoho

+4 more

Meta Bloomberg Tiktok Goldman Sachs

Topics

Hints open one at a time

Hint 1

Sort the events by the start time and in case of tie by the end time in ascending order.

Hint 2

Loop over the sorted events. Attend as much as you can and keep the last day occupied. When you try to attend new event keep in mind the first day you can attend a new event in.

11:50

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution