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. ```hint Where overlaps must show up Put the meetings in an order in which, if any two of them overlap, two neighbors must 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. ```hint What a new meeting needs to know Process the meetings by start time. When a meeting starts, which single fact about the rooms already in use decides whether it needs a new room? ``` #### 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. ```hint Think about the input you will really get Consider which inputs make a fixed pivot choice degrade, and whether real meeting lists look like those inputs. ``` #### 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? ```hint Ordered or not Treat a stream that arrives in start-time order and a stream that does not as two separate problems, and check what each one forces you to keep in memory. ``` #### 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. ```hint What append-only buys Ask what writing only at the end of a file buys a broker on disk, and what a consumer must remember to resume reading after a restart. ``` #### 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 ### What a Strong Answer Covers - Settles the touching-endpoint rule and the input order before coding - A correct heap-based Part 2 that respects the no-sweep-line rule, with a proof of minimality and precise complexity - A self-written sort with a defensible pivot strategy and an honest worst-case analysis - Streaming adaptations with explicit memory bounds - Accurate log-broker mechanics, connected back to the interval computation ### Follow-up Questions - Return which room each meeting is assigned to, not just the number of rooms. - In the streaming version, meetings can also be cancelled after they arrive. What changes? - The number of rooms is fixed at `k`. Decide, for each incoming booking request, whether it can be accepted. - Log records can arrive out of order by up to a known delay. How do you produce a correct peak without waiting forever?