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 Apple.

What role is this question designed for?

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

Compute minimum required meeting rooms

Quick Overview

This question evaluates understanding of interval scheduling and resource-allocation concepts, proficiency with data structures for detecting temporal overlaps (heap and sweep-line paradigms), and the ability to analyze time and space complexity while handling edge cases.

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given a list of meeting time intervals [start, end) for many events, determine the minimum number of rooms required so no meetings overlap in the same room. Describe and implement an algorithm using a min-heap of end times, explain its time and space complexity, and compare it with a sweep-line approach using sorted start/end times. Specify how you would handle edge cases such as zero-length meetings, identical start and end times across meetings, and very large input sizes.

Quick Answer: This question evaluates understanding of interval scheduling and resource-allocation concepts, proficiency with data structures for detecting temporal overlaps (heap and sweep-line paradigms), and the ability to analyze time and space complexity while handling edge cases.

Given a list of meeting time intervals `[start, end)` (half-open: a meeting ending at time `t` does NOT conflict with one starting at `t`), return the minimum number of conference rooms required so that no two overlapping meetings share a room. Approach (min-heap of end times): sort meetings by start time. Maintain a min-heap of the end times of meetings currently occupying rooms. For each meeting, if the earliest-freeing room (heap top) has ended at or before the new meeting's start, reuse that room (pop + push the new end); otherwise allocate a new room (push). The answer is the maximum heap size reached, which equals the final heap size after processing all meetings. Complexity: O(n log n) time (sort + heap ops), O(n) space. A sweep-line alternative sorts start and end times separately and walks both pointers, incrementing a counter on a start and decrementing on an end (process ends before equal starts to honor the half-open interval), tracking the running max — same O(n log n) time, O(n) space, no heap. Edge cases: zero-length meetings `[t, t]` occupy no time and never force an extra room when handled with `<=`; identical start/end times across meetings are handled by the half-open `end <= start` reuse check; very large inputs stay O(n log n) and the heap holds at most the peak concurrency.

Constraints

0 <= intervals.length <= 10^5
intervals[i].length == 2
0 <= start_i <= end_i <= 10^9
Intervals are half-open [start, end): a meeting ending at t does not conflict with one starting at t
Zero-length meetings [t, t] are allowed

Examples

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

Expected Output: 2

Explanation: [0,30) overlaps both [5,10) and [15,20). [5,10) and [15,20) don't overlap each other, so they can share the second room sequentially. Peak concurrency = 2.

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

Expected Output: 1

Explanation: [2,4) ends before [7,10) starts, so the single room is reused. 1 room suffices.

Input: []

Expected Output: 0

Explanation: No meetings means no rooms are needed.

Input: [[1, 5]]

Expected Output: 1

Explanation: A single meeting needs exactly one room.

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

Expected Output: 1

Explanation: Zero-length meetings [1,1) occupy no time. With the half-open rule (end <= start), each frees its room instantly, so they all reuse one room. 1 room.

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

Expected Output: 1

Explanation: Back-to-back meetings: each ends exactly when the next starts. Half-open intervals mean no overlap, so one room is reused across all three.

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

Expected Output: 4

Explanation: At time just after 11, the meetings [3,19), [8,12), [10,20), [11,30) all overlap -> peak concurrency 4.

Input: [[5, 8], [6, 8]]

Expected Output: 2

Explanation: [5,8) and [6,8) overlap on [6,8) and even share the same end time 8, so they need separate rooms simultaneously. 2 rooms.

Hints

Sort the meetings by start time so you process them in chronological order.
Track only the END times of meetings currently occupying rooms; the earliest end time is all you need to decide whether a room frees up.
A min-heap gives the earliest-freeing room in O(log n). If heap top <= current start, reuse that room (heapreplace); otherwise push a new room.
The minimum number of rooms equals the peak number of simultaneously overlapping meetings, which is the maximum heap size — and since rooms are never removed once the peak is reached only by net additions, the final heap size equals that peak.

Quick Overview