Minimum Number of Rooms to Host a Set of Possibly Overlapping Meetings

You are given the start and end times of a set of meetings. Every meeting must be held in a room, and a room can host only one meeting at a time. Return the minimum number of rooms needed to hold all of the meetings.

Function Signature

def min_rooms(meetings: list[tuple[int, int]]) -> int:

Each meeting is a pair (start, end).

Rules

• A meeting occupies its room during the half-open interval [start, end): from start up to, but not including, end.
• Two meetings can use the same room only if their intervals do not overlap. A meeting that ends at time t and another that starts at time t do not overlap, so one room can host them back to back.
• Meetings are given in no particular order, and identical meetings can appear more than once; each occurrence is a separate meeting that needs its own room time.
• Return 0 if there are no meetings.

Constraints

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

Examples

Example 1

Input: meetings = [(1, 5), (2, 6), (4, 8), (6, 9)]
Output: 3

At time 4, the meetings (1, 5), (2, 6) and (4, 8) are all in progress, so at least three rooms are needed. Three are enough: (6, 9) starts after (1, 5) has ended and can use its room.

Example 2

Input: meetings = [(1, 3), (3, 5), (5, 7)]
Output: 1

Each meeting starts exactly when the previous one ends, so one room hosts all three.

Example 3

Input: meetings = [(10, 20), (10, 20), (20, 30)]
Output: 2

The two identical meetings need separate rooms, and (20, 30) can reuse either of them.