Maximum Number of Events That Can Be Attended
Problem Description
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 startDayi <= d <= endDayi. 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 <= 105
- events[i].length == 2
- 1 <= startDayi <= endDayi <= 105
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The brute force approach involves tracking the days individually and checking which events can be attended day-by-day. For each day, check all events to see which event can finish by the current day - if none can, proceed to the next day. This method aims to maximize the number of events attended by linearly scanning available events day-by-day.
Code:
- Time Complexity: O(n * d) where
nis the number of events anddis the range of days. Typically infeasible for large inputs. - Space Complexity: O(d) where
dis the range of days for marking attended days.
2. Greedy Using a Priority Queue
Intuition:
The greedy approach utilizes a priority queue to efficiently choose events in a way that maximizes the number of days available for future events. Sort the events by their start date and use a priority queue to keep track of events that can be attended each day - this allows attending events that end the earliest if multiple events are possible on the same day.
Code:
- Time Complexity: O(n log n), where
nis the number of events due to sorting and priority queue operations. - Space Complexity: O(n), where
nis the number of events for the priority queue.