#1353

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Number of Events That Can Be Attended

Maximize the number of events you can attend given their start and end days using a greedy strategy.

array greedy sorting heap priority queue

Problem Statement

You are given a list of events where each event is represented as [startDay, endDay]. You can attend an event on any day within the range of its start and end days. However, you can only attend one event at a time, so no two events can overlap in the days you attend them.

Your task is to determine the maximum number of events you can attend. The goal is to find an optimal strategy using a greedy approach, leveraging sorting and scheduling events that do not conflict with each other.

Examples

Example 1

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

Output: 3

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

Example details omitted.

Constraints

1 <= events.length <= 105
events[i].length == 2
1 <= startDayi <= endDayi <= 105

Solution Approach

Greedy Approach with Sorting

Sort the events first by their start day, and then by their end day in case of ties. This allows you to prioritize events that start earlier and finish sooner, enabling you to attend as many events as possible.

Event Selection Strategy

After sorting, iterate through the events and select each event that starts after or exactly at the end of the previously attended event. This ensures that no two events overlap and maximizes the number of events attended.

Time Complexity Considerations

The sorting step dominates the time complexity, making the approach O(n log n), where n is the number of events. After sorting, a single pass through the events ensures the solution is efficient and scalable.

Complexity Analysis

Metric	Value
Time	O((T + n) \log n)
Space	O(n)

The time complexity is O(n log n) due to the sorting step, where n is the number of events. The space complexity is O(n) due to the storage of the events array.

What Interviewers Usually Probe

Look for knowledge of greedy algorithms and sorting.
Test the candidate's ability to implement sorting and iterate efficiently.
Assess how the candidate handles edge cases with overlapping events.

Common Pitfalls or Variants

Common pitfalls

Failing to account for tie-breaking when sorting events by end day.
Not implementing the greedy strategy properly by picking conflicting events.
Overlooking edge cases such as overlapping events with the same start and end day.

Follow-up variants

What if you had to maximize the events attended within a specific time range?
How would the problem change if events had durations instead of start and end days?
What if there were multiple event categories, and each category had a separate maximum number of events?

FAQ

How do I approach solving the Maximum Number of Events That Can Be Attended problem?

The key to solving this problem is to apply a greedy strategy. First, sort the events by their start time and end time. Then, select events that do not overlap with each other.

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

The time complexity is O(n log n) because sorting the events dominates the time complexity. The final solution is linear in the number of events.

Can you explain the greedy strategy used for the Maximum Number of Events That Can Be Attended problem?

The greedy strategy involves sorting events by their start time and end time, then selecting the earliest finishing events that do not overlap with previously selected ones.

What is the role of sorting in solving the Maximum Number of Events That Can Be Attended problem?

Sorting the events helps in selecting events that allow for the maximum number of attendable events. By sorting by start and end times, the approach ensures optimal scheduling.

How can I optimize my solution to the Maximum Number of Events That Can Be Attended problem?

Optimize your solution by focusing on efficient sorting and selecting events in a single pass. Ensure that you handle tie-breaking correctly and test for edge cases.

terminal

Solution

Solution 1: Hash Table + Greedy + Priority Queue

We use a hash table $\textit{g}$ to record the start and end times of each event. The key is the start time of the event, and the value is a list containing the end times of all events that start at that time. Two variables, $\textit{l}$ and $\textit{r}$, are used to record the minimum start time and the maximum end time among all events.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        g = defaultdict(list)
        l, r = inf, 0
        for s, e in events:
            g[s].append(e)
            l = min(l, s)
            r = max(r, e)
        pq = []
        ans = 0
        for s in range(l, r + 1):
            while pq and pq[0] < s:
                heappop(pq)
            for e in g[s]:
                heappush(pq, e)
            if pq:
                heappop(pq)
                ans += 1
        return ans

Continue Practicing

#1338 reduce array size to the half #1383 maximum performance of a team #1648 sell diminishing valued colored balls