Katkat
Back

Find Any Available Meeting Room

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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. 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.