How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Apple.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Apple during technical interviews.

Compute conflicts and minimum meeting rooms

Q: Compute conflicts and minimum meeting rooms

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.

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.

Input: []

Expected Output: True

Explanation: With no meetings, one room is trivially sufficient.

Input: [[4, 6], [1, 2], [2, 4], [6, 9]]

Expected Output: True

Explanation: After sorting, each meeting starts exactly when the previous one ends or later, so there is no overlap.

Input: [[1, 4], [2, 3]]

Expected Output: False

Explanation: The interval [2, 3) is fully inside [1, 4), so the meetings overlap.

Solution

def solution(intervals):
    if not intervals:
        return True

    intervals = sorted(intervals, key=lambda x: (x[0], x[1]))
    prev_end = intervals[0][1]

    for start, end in intervals[1:]:
        if start < prev_end:
            return False
        prev_end = end

    return True

Time complexity: O(n log n). Space complexity: O(n).

Hints

Try sorting the meetings by their start time first.
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.

Input: []

Expected Output: 0

Explanation: No meetings means no rooms are needed.

Input: [[1, 10], [2, 7], [3, 19], [8, 12], [10, 20], [11, 30]]

Expected Output: 4

Explanation: The maximum number of simultaneous meetings is four, which happens after the meeting starting at 11 begins.

Input: [[1, 4], [1, 4], [1, 4]]

Expected Output: 3

Explanation: All three meetings start at the same time, so they require three different rooms.

Solution

def solution(intervals):
    import heapq

    if not intervals:
        return 0

    intervals = sorted(intervals, key=lambda x: (x[0], x[1]))
    heap = []
    max_rooms = 0

    for start, end in intervals:
        while heap and heap[0] <= start:
            heapq.heappop(heap)
        heapq.heappush(heap, end)
        if len(heap) > max_rooms:
            max_rooms = len(heap)

    return max_rooms

Time complexity: O(n log n). Space complexity: O(n).

Hints

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

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.