You are given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.
You can attend an event i at any day d where startTimei <= d <= endTimei. 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 <= 105events[i].length == 21 <= startDayi <= endDayi <= 105The idea is to sort the events by their end days. By doing this, you give preference to events that finish earliest, thus maximizing the number of events you can attend. You use a set to record which days are occupied. For each event, try to attend it on the earliest possible day starting from the event's start day.
The solution begins by sorting the events on their end days. We then iterate over the events and try to attend them at the earliest possible day that is still unoccupied. A boolean array is used to mark the days that have been occupied. This helps efficiently manage which days have been taken up by events, ensuring that no two events are attended on the same day.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N log N), where N is the number of events, due to sorting.
Space Complexity: O(1), considering the constraint that the maximum day value does not exceed 100,000.
In this approach, we leverage a priority queue (implemented using a min-heap) to choose the next event to attend. By adding each event's end day to the heap, we can focus on attending the event that ends first among the available ones. We iterate over the days and use the priority queue to ensure the event attended finishes at the earliest possible time, freeing up subsequent days for potentially more events.
The C++ solution uses a priority queue to manage events by their end times. By popping the smallest element (earliest end time), the code guarantees that it tries to attend the event that leaves most days open for future events, allowing more to be attended overall.
Python
Time Complexity: O(N log N), with N log N for sorting and N log N for priority queue operations.
Space Complexity: O(N) for the priority queue.
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Approach with Sorting and Set | Time Complexity: O(N log N), where N is the number of events, due to sorting. |
| Approach 2: Priority Queue (Min-Heap) Method | Time Complexity: O(N log N), with N log N for sorting and N log N for priority queue operations. |
Leetcode 1353. Maximum Number of Events That Can Be Attended • Fraz • 32,349 views views
Watch 9 more video solutions →Practice Maximum Number of Events That Can Be Attended with our built-in code editor and test cases.
Practice on FleetCode