Quick Overview

This question evaluates the ability to reason about interval overlaps and resource allocation, testing algorithmic thinking and efficient handling of time-interval data in scheduling contexts and belongs to the Coding & Algorithms domain.

Compute conflicts and minimum meeting rooms

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a list of meeting room booking requests. Each request is a half-open time interval **[start, end)**, meaning it uses the room starting at `start` and releases it at `end` (so a meeting ending at time `t` does **not** overlap one starting at time `t`). A single meeting room can host **at most one** request at any time. ### Tasks 1. **Feasibility with one room:** Determine whether **all** requests can be satisfied using **only one** meeting room (i.e., no time overlaps). 2. **Minimum rooms needed:** If one room is not enough, compute the **minimum number of meeting rooms** required so that **all** requests can be satisfied. ### Input / Output - **Input:** An array/list `intervals` of length `n`, where each element is `[start, end)` with `start < end`. - **Output:** - A boolean `canScheduleInOneRoom`. - An integer `minRooms` (the minimum number of rooms needed). ### Constraints (assume) - `1 ≤ n ≤ 10^5` - `start` and `end` are integers (or comparable timestamps) within a reasonable range. ### Example - Input: `[[0, 30], [5, 10], [15, 20]]` - Output: `canScheduleInOneRoom = false`, `minRooms = 2`

Quick Answer: This question evaluates the ability to reason about interval overlaps and resource allocation, testing algorithmic thinking and efficient handling of time-interval data in scheduling contexts and belongs to the Coding & Algorithms domain.

Part 1: Can All Meetings Fit in One Room?

You are given a list of meeting requests, where each request is a half-open interval [start, end). A meeting uses the room starting at time start and releases it at time end, so a meeting ending at time t does not conflict with one starting at time t. Determine whether all meetings can be scheduled using only one meeting room. Return True if no two meetings overlap in time; otherwise return False.

Constraints

  • 0 <= n <= 10^5, where n is the number of intervals
  • Each interval has exactly two integers: start and end
  • For every interval, start < end
  • Intervals are half-open: [start, end)

Examples

Input: [[0, 30], [5, 10], [15, 20]]

Expected Output: False

Explanation: The meeting [0, 30) overlaps with both [5, 10) and [15, 20), so one room is not enough.

Input: [[1, 3], [3, 5], [5, 8]]

Expected Output: True

Explanation: These meetings only touch at boundaries. Because the intervals are half-open, they do not overlap.

Hints

  1. Try sorting the meetings by their start time first.
  2. After sorting, it is enough to compare each meeting with the one that ends most recently before it.

Part 2: Minimum Number of Meeting Rooms

You are given a list of meeting requests, where each request is a half-open interval [start, end). A meeting ending at time t does not overlap with a meeting starting at time t. Compute the minimum number of meeting rooms required so that all meetings can be scheduled.

Constraints

  • 0 <= n <= 10^5, where n is the number of intervals
  • Each interval has exactly two integers: start and end
  • For every interval, start < end
  • Intervals are half-open: [start, end)

Examples

Input: [[0, 30], [5, 10], [15, 20]]

Expected Output: 2

Explanation: At most two meetings overlap at once, so two rooms are required.

Input: [[1, 3], [3, 5], [5, 8]]

Expected Output: 1

Explanation: Each meeting starts exactly when the previous one ends, so one room can be reused.

Hints

  1. If you process meetings in start-time order, you only need to know which scheduled meeting ends earliest.
  2. A min-heap of end times is a good way to reuse rooms as soon as they become free.

Loading coding console...