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 medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

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

Compute minimum number of rooms needed

Q: Compute minimum number of rooms needed

This question evaluates a candidate's ability to reason about overlapping intervals and resource allocation, testing algorithmic problem-solving skills and familiarity with data structures for scheduling conflicts.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem You are given a list of meetings, each with a start time and end time. A single room can host only one meeting at a time. Two meetings **overlap** if one starts before the other ends (treat meetings as half-open intervals **[start, end)** so a meeting ending at time `t` does not conflict with another starting at time `t`). ### Task Return the **minimum number of rooms** required to host all meetings. ### Input - `intervals`: an array of `n` pairs `[start, end]` where `0 <= start <= end`. ### Output - An integer: the minimum number of rooms needed. ### Constraints (typical interview bounds) - `1 <= n <= 200000` - Times are integers in a reasonable range (e.g., `0 .. 10^9`). ### Example - Input: `[[0,30],[5,10],[15,20]]` - Output: `2` (One room can host `[0,30]`, the other can host `[5,10]` then `[15,20]`.)

Quick Answer: This question evaluates a candidate's ability to reason about overlapping intervals and resource allocation, testing algorithmic problem-solving skills and familiarity with data structures for scheduling conflicts.

You are given a list of meetings, where each meeting is represented as [start, end]. A single room can host only one meeting at a time. Meetings are treated as half-open intervals [start, end), so a meeting ending at time t does not conflict with another meeting starting at time t. Return the minimum number of rooms required to host all meetings. If start == end, the meeting occupies no time and does not require a room.

Constraints

0 <= n <= 200000
0 <= start <= end <= 10^9

Examples

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

Expected Output: 2

Explanation: [0,30] overlaps with both [5,10] and [15,20], so at most 2 rooms are needed at the same time.

Input: ([[7,10],[2,4],[4,7],[10,12]],)

Expected Output: 1

Explanation: These meetings only touch at endpoints, so one room can host all of them in sequence.

Input: ([[1,5],[2,6],[3,7],[4,8]],)

Expected Output: 4

Explanation: All four meetings overlap during the time interval [4,5), so 4 rooms are required.

Input: ([[1,4],[1,4],[1,4],[4,5]],)

Expected Output: 3

Explanation: Three identical meetings overlap fully from time 1 to 4. The meeting [4,5] starts exactly when they end, so it can reuse a room.

Input: ([],)

Expected Output: 0

Explanation: No meetings means no rooms are needed.

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

Expected Output: 1

Explanation: Zero-length meetings occupy no time. The only real meetings are [2,3] and [3,4], which do not overlap.

Solution

def solution(intervals):
    events = []

    for start, end in intervals:
        # [start, end) with start == end is an empty interval.
        if start == end:
            continue
        events.append((start, 1))
        events.append((end, -1))

    # Process ending events before starting events at the same time.
    events.sort(key=lambda event: (event[0], event[1]))

    rooms_in_use = 0
    max_rooms = 0

    for _, delta in events:
        rooms_in_use += delta
        if rooms_in_use > max_rooms:
            max_rooms = rooms_in_use

    return max_rooms

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

Hints

Try turning each meeting into two events: one when it starts and one when it ends.
Because intervals are half-open, if a meeting ends at the same time another starts, process the ending event first.

Quick Overview

This question evaluates a candidate's ability to reason about overlapping intervals and resource allocation, testing algorithmic problem-solving skills and familiarity with data structures for scheduling conflicts.