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 ```python 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** ```text 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** ```text 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** ```text 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.