Problem Description
You are given an array of events where events[i] = [startDay_i, endDay_i]. Every event i starts at startDay_i and ends at endDay_i. You can attend an event i at any day d where startDay_i <= d <= endDay_i. You can only attend one event at any time d. Return the maximum number of events you can attend.
Key Insights
- Each event has a defined start and end day, creating a range of days during which it can be attended.
- Events can overlap, making it crucial to select days wisely to maximize attendance.
- A greedy algorithm is effective for this problem, where we prioritize events based on their end days to minimize conflicts.
- Sorting the events by their end days allows us to make optimal choices for attending events.
Space and Time Complexity
Time Complexity: O(n log n) - due to sorting the events. Space Complexity: O(n) - to store the events and manage the days we attend.
Solution
To solve the problem, we can use a greedy approach. We first sort the events by their end days. Then, we iterate through the sorted list and keep track of the days we've attended events. By always choosing the earliest available day to attend an event, we ensure that we can maximize the number of events we can attend without overlap. We maintain a set of days to track which days have already been attended.