Problem Statement

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.

Examples

Example 1:

Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all three events.
- 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
Explanation: You can attend all four events.
- Attend one [1,2] event on day 1
- Attend another [1,2] event on day 2
- Attend [2,3] event on day 3
- Attend [3,4] event on day 4

Understanding the Problem

This is a classic interval scheduling problem with a twist. Unlike traditional interval scheduling, where we pick non-overlapping intervals, here we can attend overlapping events as long as we attend them on different days.

Some Key Insights

1. Greedy Strategy: We should prioritize events that have fewer scheduling options (end sooner)
2. Flexibility: Events with longer durations give us more flexibility in scheduling
3. One Event Per Day: We can only attend one event per day, so we need to make optimal choices

Approach 1: Naive Greedy (Time Limit Exceeded)

Let's start with the intuitive approach to understand the problem better. This was my first approach, but got Time Limit Exceeded

Algorithm

1. Sort events by end day (attend events that end earlier first)
2. For each event, try to attend it on the earliest available day