Minimum Meeting Rooms Without a Sweep Line
Updated
Problem statement
You are given a finite collection of meetings. Each row [start, end] represents a half-open interval [start, end). Return the minimum number of rooms needed to hold every meeting. A room may host another meeting exactly when the previous meeting ends.
For this exercise, assume input order is arbitrary, every meeting must be held, duplicate rows represent separate meetings, and an empty collection needs zero rooms. Return the room count, not a room assignment.
Solve the task without a sweep-line event scan. A follow-up asks how to avoid a built-in sorting routine; both presented heap-based solutions avoid one.
Interview follow-ups
The interviewer asked for heap complexity, an alternative to sort(), pivot selection and streaming input. Discuss a heap of arrival records, a manually implemented comparison sort, and the difference between a stream already ordered by start time and an arbitrary stream that cannot yet be finalized. The author later interpreted a question about replacing intervals with logs as possibly relating to append-only brokers; that interpretation is not a required Kafka or log-processing interface.
Function
minMeetingRooms(intervals: int[][]) → intExamples
Example 1
intervals = [[0,30],[5,10],[15,20]]return = 2The meeting [0,30) overlaps each shorter meeting. The shorter meetings do not overlap each other, so two rooms suffice and one cannot suffice.
Example 2
intervals = [[7,10],[2,4]]return = 1The input is not in start-time order, but the two meetings are disjoint. One room can host both.
Example 3
intervals = []return = 0There are no meetings, so no room is required.
Constraints
- For this exercise, assume
0 <= intervals.length <= 2000. - Every interval row contains exactly
2integers. - Every endpoint is between
0and1000000000. - Each row satisfies
start < end.
More Goldman Sachs Onsite Interview questions
- Knight Probability in ChessboardONSITE INTERVIEW · Seen Nov 2026
- Best Average Student ScorePHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Meeting RoomsPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- First Non-Repeating CharacterPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Root of the Largest TreePHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Dungeon HealthONSITE INTERVIEW · Seen Sep 2026
- Insert, Delete, And Get Random In Constant TimeONSITE INTERVIEW · Seen Sep 2026
- Least Recently Used CacheONSITE INTERVIEW · Seen Sep 2026
- Staircase Search In A Sorted MatrixONSITE INTERVIEW · Seen Sep 2026
- Maximize Element FrequencyONSITE INTERVIEW · Seen Sep 2026
Similar questions at other companies
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Retrieve Vectors by Cosine SimilarityHarvey · ONSITE INTERVIEWHarvey interview questions
- Top K Largest Values from a StreamThe D.E. Shaw Group · ONSITE INTERVIEWThe D.E. Shaw Group interview questions
- Generate Complete Inputs for a Supplied ClassifierGeneral Motors · ONSITE INTERVIEW
- Dominant Index with Strict Doubling GapsGoogle · ONSITE INTERVIEWGoogle interview questions
- Top K Largest Values with a HeapMeta · ONSITE INTERVIEWMeta interview questions
- Top K Frequent ElementsCapgemini · ONSITE INTERVIEWCapgemini interview questions
- Select K Paired Indices for Maximum ScoreAmazon · ONSITE INTERVIEW
- Kth Largest Element in an ArrayOneTrust · ONSITE INTERVIEW
- Kth Largest Element in an ArrayCognizant · ONSITE INTERVIEW