Most Meetings You Can Attend When Each Takes One Day Within Its Range

You are given a list of meetings, each of which can be attended on any one day within a range of days. Attending a meeting takes one whole day, and you can attend at most one meeting per day. Return the largest number of meetings you can attend.

Function Signature

def max_meetings_attended(meetings: list[list[int]]) -> int:

Rules

• meetings[i] = [start, end] means meeting i can be attended on any single day d with start <= d <= end; both ends are inclusive.
• Each meeting counts at most once, and each day can be used for at most one meeting.

Constraints

• 1 <= len(meetings) <= 10^5
• 1 <= start <= end <= 10^5 for every meeting

Examples

Example 1

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

The two meetings over days 1 to 2 take days 1 and 2, the meeting over days 2 to 3 takes day 3, and the meeting over days 3 to 4 takes day 4.

Example 2

Input: meetings = [[1, 1], [1, 1], [1, 2]]
Output: 2

Both meetings that are available only on day 1 need that day, so only one of them can be attended; the third takes day 2.

Example 3

Input: meetings = [[1, 2], [1, 2], [1, 2], [3, 3]]
Output: 3

Only two of the three meetings over days 1 to 2 fit, and the last meeting takes day 3.