Overlapping Meetings and Minimum Rooms: No Sweep Line, No Library Sort, Streams, Logs

You are given a list of meetings, each with an integer start time and end time, start < end. This round was a chain of questions on the same input, each building on the previous answer.

Clarifying Questions

• If one meeting ends at 10 and another starts at 10, do they conflict?
• Can the list be empty, and can two meetings be identical?
• Is the list already sorted by start time?
• How large can the list be, and what range do the times cover?

Part 1 — Can one person attend every meeting?

As a warm-up, return whether a single person could attend all of the meetings, that is, whether no two meetings overlap.

What This Part Should Cover

• The ordering argument that makes a neighbor check sufficient
• The boundary rule for meetings that touch
• Time and space complexity

Part 2 — Minimum number of rooms, without a sweep line

Return the minimum number of meeting rooms needed so that every meeting has a room and no room hosts two overlapping meetings. The interviewer ruled out the sweep-line approach (turning starts and ends into separately sorted event lists, or into +1 and −1 events, and counting). Analyze the time and space complexity in detail.

What This Part Should Cover

• An argument that the algorithm uses the minimum number of rooms
• The data structure and the cost of each operation on it
• Best-case and worst-case behavior, and where each logarithmic factor comes from

Part 3 — No library sort

Now suppose you may not call a built-in sort. Put the meetings in order yourself, and expect to be asked how you choose a pivot.

What This Part Should Cover

• A working in-place ordering routine with its expected and worst-case cost
• Pivot strategies and the inputs that defeat each one, including many equal start times
• Alternatives that avoid a comparison sort or a separate sorting step

Part 4 — Meetings arrive as a stream

The meetings now arrive one at a time instead of as a complete list. How do your answers to Parts 1 and 2 change?

Clarifying Questions for this Part

• Do meetings arrive in order of start time, or in any order?
• Is the answer needed after every arrival, or only at the end?
• Can meetings that have already ended be forgotten?

What This Part Should Cover

• An online version of Part 2 for a stream ordered by start time, with its memory bound
• What breaks when arrivals are out of order, and a structure or buffering strategy that copes
• Reporting a running answer

Part 5 — From intervals to logs

Finally, the interviewer reframed the input: suppose these arrays are not meeting times but logs. The candidate was not sure what was wanted; the discussion seemed to lead toward how a log-based message broker such as Kafka works, with its append-only log. Explain how such a broker stores and serves an append-only log, and, assuming each log record carries a start and an end time, how the Part 2 computation would run over records arriving through it.

What This Part Should Cover

• Partitions, offsets and segment files, and why appends and sequential reads are cheap
• Consumers, consumer groups and committed offsets; replication, and when a record counts as committed
• Ordering guarantees, and what they mean for computing overlaps over records that carry time intervals