Find Any Available Meeting Room
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Interview Round: Onsite
You are given multiple meeting rooms. For each room, the existing bookings are represented as a list of non-overlapping time intervals sorted by start time. Each interval is half-open: `[start, end)`.
Given a new meeting interval `[s, e)`, return the identifier of **any** room where the new meeting can be inserted without overlapping an existing booking. If multiple rooms are valid, returning the first valid one is acceptable. If no room can hold the meeting, return `-1`.
A booking `[s, e)` can be inserted into a room if it does not overlap any existing interval in that room.
Example:
- Room 0: `[[1, 3], [5, 7]]`
- Room 1: `[[2, 4], [8, 10]]`
- New meeting: `[3, 5)`
- Valid answer: `0`
Design an efficient algorithm. A straightforward solution may check rooms one by one, but within each room you should avoid scanning every existing meeting if the room's bookings are already sorted.
Quick Answer: This question evaluates a candidate's competence in handling interval-based scheduling problems, specifically managing interval data and performing efficient searches within sorted bookings to detect potential overlaps.
You are given multiple meeting rooms. Room i has a schedule represented by a list of non-overlapping booking intervals sorted by start time. Each interval is half-open: [start, end), so two meetings that only touch at an endpoint do not overlap.
Given a new meeting interval [s, e), return the identifier of the first room (smallest index) where the meeting can be inserted without overlapping any existing booking. If no room can hold the meeting, return -1.
You should design an efficient algorithm: rooms may be checked one by one, but inside each room you should use the fact that its bookings are already sorted instead of scanning every booking linearly.
Constraints
- 0 <= len(rooms) <= 10^5
- 0 <= total number of existing bookings across all rooms <= 2 * 10^5
- Each booking interval satisfies start < end
- Each room's bookings are sorted by start time and do not overlap
- -10^9 <= start < end <= 10^9 for all times
Examples
Input: ([[[1, 3], [5, 7]], [[2, 4], [8, 10]]], [3, 5])
Expected Output: 0
Explanation: In room 0, [3, 5) fits exactly between [1, 3) and [5, 7) because touching endpoints is allowed.
Input: ([[[1, 2], [4, 6]], [], [[0, 10]]], [2, 4])
Expected Output: 0
Explanation: The new meeting fits exactly in the gap of room 0. Although room 1 is also empty, the first valid room index is 0.