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

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.

Loading coding console...

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