Online Meeting Scheduler with Fixed Rooms
Uber● MediumFULLTIMEONSITE INTERVIEWProblem statement
You have n meeting rooms, numbered 0 through n - 1, and an array requests. Each request is [start, end] and asks to book the half-open interval [start, end).
Treat the array as calls to one fresh meeting scheduler. Every room starts empty. Process requests in their given order; requests may arrive in any time order.
- Choose the smallest room ID that is free for the whole requested interval.
- Accepted bookings stay fixed. Never move, shorten, remove, or preempt an earlier booking.
- If every room conflicts, record
-1and leave all calendars unchanged. - Intervals that only touch at an endpoint do not overlap. For example,
[1,5)and[5,8)may share a room.
Return one integer per request: its booked room ID, or -1 on failure. An empty request array returns an empty result.
Function
scheduleMeetings(n: int, requests: int[][]) → int[]Examples
Example 1
n = 1requests = [[1,5],[5,8]]return = [0,0]Book [1,5) in room 0. The next request [5,8) starts exactly when that booking ends, so it also uses room 0. The result is [0,0].
Example 2
n = 2requests = [[1,5],[2,4],[3,6],[4,5],[5,7]]return = [0,1,-1,1,0]The first two requests occupy rooms 0 and 1. Request [3,6) overlaps both and fails. Request [4,5) fits room 1 because its earlier booking ends at 4. Request [5,7) can use both rooms, so choose room 0. The result is [0,1,-1,1,0].
Example 3
n = 1requests = [[10,20],[0,5],[5,10],[4,6]]return = [0,0,0,-1]Room 0 accepts [10,20), then the earlier disjoint interval [0,5), then the gap [5,10). The last request [4,6) overlaps accepted bookings and fails. The result is [0,0,0,-1].
Constraints
1 <= n <= 100.0 <= requests.length <= 5000.requests[i].length == 2.0 <= requests[i][j] <= 10^9.- Each request has
start < end. - The numeric bounds and nonempty-interval requirement are practice assumptions.