Assign meetings to rooms with delays

You are given:

• An integer n (number of meeting rooms, labeled 0..n-1 ).
• A list of m meetings meetings[i] = [start_i, end_i) with start_i < end_i .

All meetings are processed in increasing order of start_i (if two meetings have the same start time, process the one with the earlier end time first).

Scheduling rules:

1. If at time start_i there is at least one free room, assign the meeting to the free room with the smallest index. The meeting runs during [start_i, end_i) .
2. If no rooms are free at time start_i , you must delay the meeting: wait until the room that becomes available the earliest is free (if multiple rooms free at the same earliest time, pick the smallest index). Then start the meeting immediately at that time, keeping the same duration (end_i - start_i) .

After all meetings are scheduled, return the room index that was used for the largest number of meetings. If there is a tie, return the smallest room index.

Input

• n : integer
• meetings : list of pairs [start, end)

Output

• Integer room index

Constraints (typical)

• 1 <= n <= 10^3
• 1 <= m <= 2*10^5
• 0 <= start_i < end_i <= 10^9

(Implementation should be efficient enough for large m.)