Maximize Events Attended When Each Spans a Day Range and One Fits per Day
Company: ByteDance
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a list of events. Each event can be attended on any one whole day from its start day to its end day, inclusive. You can attend at most one event per day, and attending an event on one of its days counts as attending that event. Return the maximum number of events you can attend.
### Function Signature
```python
def max_events_attended(events: list[list[int]]) -> int:
```
### Rules
- `events[i] = [start_i, end_i]` with integer days; event i may be attended on exactly one day `d` with `start_i <= d <= end_i`.
- On each day at most one event is attended, and each event is attended at most once.
- Events may overlap, share the same range, or repeat; every list entry is a separate event.
- Return the largest possible number of attended events as a single integer.
### Constraints
- `1 <= len(events) <= 10^5`
- `1 <= start_i <= end_i <= 10^5`
### Examples
**Example 1**
```text
Input: events = [[1, 2], [1, 2], [1, 2], [2, 4]]
Output: 3
```
The three events covering days 1 to 2 have only two days between them, so at most two of them are attended, on days 1 and 2. The event covering days 2 to 4 is attended on day 3.
**Example 2**
```text
Input: events = [[1, 5], [1, 1], [2, 2], [5, 5], [3, 4]]
Output: 5
```
All five can be attended: `[1, 1]` on day 1, `[2, 2]` on day 2, `[3, 4]` on day 3, `[1, 5]` on day 4 and `[5, 5]` on day 5.
**Example 3**
```text
Input: events = [[3, 3], [3, 3], [3, 3]]
Output: 1
```
All three events can only be attended on day 3, which holds one event.
Overview: A coding problem: given events that can each be attended on any one day within their start-to-end day range, with at most one event per day, return the maximum number of events that can be attended. It tests reasoning about overlapping intervals and an efficient solution for up to 100,000 events and days.
You are given a list `events`, where `events[i] = [start_i, end_i]` gives the whole days on which event `i` can be attended: any one day `d` with `start_i <= d <= end_i` (both ends inclusive).
You can attend at most one event per day, and each event is attended at most once. Attending an event on one of its days counts as attending that event. Events may overlap, share the same range, or repeat, and every list entry is a separate event.
Return the maximum number of events you can attend, as a single integer.
**Constraints**
- `1 <= len(events) <= 10^5`
- `1 <= start_i <= end_i <= 10^5`
- Every day value and the answer (at most `len(events)`) fit in a signed 32-bit integer; no value exceeds 2^31 - 1.
**Example 1**
```text
Input: events = [[1, 2], [1, 2], [1, 2], [2, 4]]
Output: 3
```
The three events covering days 1 to 2 have only two days between them, so at most two of them are attended, on days 1 and 2. The event covering days 2 to 4 is attended on day 3.
**Example 2**
```text
Input: events = [[1, 5], [1, 1], [2, 2], [5, 5], [3, 4]]
Output: 5
```
All five can be attended: `[1, 1]` on day 1, `[2, 2]` on day 2, `[3, 4]` on day 3, `[1, 5]` on day 4 and `[5, 5]` on day 5.
Constraints
- 1 <= len(events) <= 10^5
- 1 <= start_i <= end_i <= 10^5
- events[i] = [start_i, end_i] holds two integer days; event i may be attended on exactly one day d with start_i <= d <= end_i
- At most one event is attended per day and each event at most once; repeated ranges are separate events
- All day values and the answer fit in a signed 32-bit integer
Examples
Input: ([[1, 1]],)
Expected Output: 1
Explanation: Minimum valid input: one event whose only day is day 1.
Input: ([[1, 100000]],)
Expected Output: 1
Explanation: Single wide event spanning the full day range 1 to 100000 is attended exactly once.
Hints
- Look at Example 1: events whose ranges all lie inside the same few days can contribute at most as many events as there are days in that window.
- Consider the days in increasing order and keep track of which events have already started but have been neither attended nor missed.
- When several of those events could use today's slot, think about which one would be hardest to fit in on a later day.