Assign Meetings to the Minimum Number of Rooms

Problem Statement

You are given an array of meeting intervals meetings, where meetings[i] = [start_i, end_i] represents a meeting taking place in the half-open time interval [start_i, end_i). A meeting ending at time t frees its room immediately, allowing another meeting starting at time t to use the same room.

Your task is to assign each meeting to a room such that no two overlapping meetings share the same room, while satisfying the following deterministic allocation rules:

1. Meetings are processed in ascending order of their start time. If two meetings have the same start time, process the one with the smaller original index first.
2. Before scheduling a meeting at time start, all rooms containing meetings with end <= start are vacated.
3. The meeting is assigned to the smallest available room ID (0-indexed). If no rooms are currently free, allocate a new room with an ID equal to the total number of rooms created so far (e.g., 0, then 1, then 2, ...).

Return an integer array result of length len(meetings), where result[i] is the room ID assigned to meetings[i] in the original input order.

Function Signature

def assign_rooms(meetings: list[list[int]]) -> list[int]:
    pass

Examples

Example 1

Input: meetings = [[0, 30], [5, 10], [15, 20]]
Output: [0, 1, 1]
Explanation:
- Meeting 0 [0, 30] arrives at t=0. No rooms exist; room 0 is allocated.
- Meeting 1 [5, 10] arrives at t=5. Room 0 is busy until 30; room 1 is allocated.
- Meeting 2 [15, 20] arrives at t=15. Meeting 1 ended at t=10, so room 1 is free. Smallest free room is 1. Room 1 is assigned.

Example 2

Input: meetings = [[1, 4], [2, 5], [4, 6]]
Output: [0, 1, 0]
Explanation:
- Meeting 0 [1, 4] is assigned to room 0.
- Meeting 1 [2, 5] is assigned to room 1.
- Meeting 2 [4, 6] arrives at t=4. Meeting 0 ended at t=4 (half-open interval), releasing room 0. The smallest free room is 0, so room 0 is assigned.

Constraints

• 1 <= len(meetings) <= 10^5
• meetings[i].length == 2
• 0 <= start_i < end_i <= 10^9

Edge Cases

• Consecutive non-overlapping meetings (e.g., [1, 2], [2, 3]): should both reuse room 0.
• Identical start times: ensure stable ordering by original index.