You are given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayiand 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.
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.
For each time point \(s\) from \(\textit{l}\) to \(\textit{r}\) in increasing order, we perform the following steps:
Remove from the priority queue all events whose end time is less than the current time \(s\).
Add the end times of all events that start at the current time \(s\) to the priority queue.
If the priority queue is not empty, take out the event with the earliest end time, increment the answer count, and remove this event from the priority queue.
In this way, we ensure that at each time point \(s\), we always attend the event that ends the earliest, thus maximizing the number of events attended.
The time complexity is \(O(M \times \log n)\), and the space complexity is \(O(n)\), where \(M\) is the maximum end time and \(n\) is the number of events.