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.

Find Minimum Rooms Needed | Google Coding Question

Q: Find Minimum Rooms Needed

This question evaluates understanding of interval scheduling and conflict detection in time ranges, along with algorithmic reasoning and appropriate data structure use for managing concurrent events and resource allocation.

Find Minimum Rooms Needed

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list of meeting intervals, where each interval is represented as `[start, end)` and `start < end`. Two meetings conflict if their time ranges overlap. Determine the minimum number of rooms required so that all meetings can be scheduled without conflicts. Example: - Input: `[[0, 30], [5, 10], [15, 20]]` - Output: `2` A simple follow-up is to explain how you would also produce one valid room assignment for each meeting.

Quick Answer: This question evaluates understanding of interval scheduling and conflict detection in time ranges, along with algorithmic reasoning and appropriate data structure use for managing concurrent events and resource allocation.

Part 1: Minimum Number of Meeting Rooms

You are given a list of meeting intervals, where each interval is represented as [start, end) and start < end. Intervals are half-open, so a meeting ending at time t does not conflict with a meeting starting at time t. Return the minimum number of rooms required so that every meeting can be scheduled without overlap.

Constraints

0 <= n <= 200000, where n is the number of meetings
-10^9 <= start < end <= 10^9
Intervals are half-open: [start, end), so end == next_start does not overlap

Examples

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

Expected Output: 2

Explanation: The meeting [0, 30) overlaps with both later meetings, so two rooms are needed.

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

Expected Output: 1

Explanation: Because intervals are half-open, each meeting starts exactly when the previous one ends, so one room is enough.

Input: []

Expected Output: 0

Explanation: No meetings means no rooms are required.

Input: [[7, 10], [2, 4]]

Expected Output: 1

Explanation: These meetings do not overlap, even though the input is unsorted.

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

Expected Output: 3

Explanation: At time 4, three meetings are active: [1, 5), [2, 6), and [4, 8).

Hints

Sort meetings by start time. As you scan from left to right, keep track of meetings that are still in progress.
A min-heap of end times lets you quickly find the room that becomes free the earliest.

Part 2: Produce a Valid Meeting Room Assignment

You are given a list of meeting intervals, where each interval is represented as [start, end) and start < end. Assign every meeting to a room so that no two overlapping meetings use the same room. To make the answer deterministic, follow these rules: 1. Room numbers start at 0. 2. Process meetings in increasing order of start time; if two meetings have the same start time, process the one with the smaller original index first. 3. Before assigning a meeting, any room whose current meeting ends at or before the new meeting's start time becomes available. 4. Always assign the smallest available room number. If none are available, create a new room. Return the room number assigned to each meeting in the original input order.

Constraints

0 <= n <= 200000, where n is the number of meetings
-10^9 <= start < end <= 10^9
Intervals are half-open: [start, end), so end == next_start does not overlap
Room numbers must start at 0 and use the smallest available room under the stated rules

Examples

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

Expected Output: [0, 1, 1]

Explanation: Meeting 0 gets room 0. Meeting 1 overlaps with it, so it gets room 1. Meeting 2 can reuse room 1 after meeting 1 ends.

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

Expected Output: [0, 0, 0]

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

Input: []

Expected Output: []

Explanation: No meetings means no assignments.

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

Expected Output: [1, 0, 1, 0]

Explanation: After sorting by start time, room 0 is used by [0, 30), room 1 by [5, 10), room 1 is reused for [15, 20), and room 0 is reused for [30, 40).

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

Expected Output: [0, 1, 2]

Explanation: All meetings start at the same time, so none can share a room. They are processed in original index order.

Hints

Use one min-heap for active rooms keyed by meeting end time, and another min-heap for room numbers that are currently free.
Sort meetings by (start time, original index) so that the output is deterministic.

Quick Overview

This question evaluates understanding of interval scheduling and conflict detection in time ranges, along with algorithmic reasoning and appropriate data structure use for managing concurrent events and resource allocation.