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. Notice that 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


Example 3:

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


Example 4:

Input: events = [[1,100000]]
Output: 1


Example 5:

Input: events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
Output: 7


Constraints:

• 1 <= events.length <= 10^5
• events[i].length == 2
• 1 <= events[i] <= events[i] <= 10^5

## Solution: Greedy

Sort events by end time, for each event find the first available day to attend.

Time complexity: O(sum(endtime – starttime)) = O(10^10)
Space complexity: O(max(endtime – starttime) = O(10^5)

## Python

We can use a TreeSet to maintain the open days and do a binary search to find the first available day.

Time complexity: O(nlogd)
Space complexity: O(d)

## C++

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website 