Minimum Rooms, Merged Busy Blocks and Conflict Handling for Meeting Intervals

You are given a list of meetings, each a pair `[start, end]` of integer times with `start < end`. The coding round opened with the classic meeting-room problem and then asked two follow-ups: how to merge meetings whose start and end times differ, and how to handle conflicts. The exact details of the follow-ups were not reported, and the interviewer mainly wanted a clearly explained approach, so each Part below states the standard form of its question and leaves the open policies as clarifying questions. Unless the interviewer says otherwise, treat a meeting as the half-open interval from `start` up to but not including `end`, so a meeting that ends at 10 and one that starts at 10 do not overlap. ```text meetings = [[9, 10], [9, 12], [11, 13], [14, 15]] minimum number of rooms -> 2 merged busy blocks -> [[9, 13], [14, 15]] meetings overlapping [12, 14] -> [[11, 13]] ``` ### Clarifying Questions - Should meetings that share an endpoint, such as `[9, 10]` and `[10, 11]`, count as overlapping? - Are all meetings known up front, or do booking requests arrive one at a time and need an immediate answer? - How many meetings can there be, and may the input list be reordered in place? - When a conflict is found, should it be reported, rejected, or resolved by moving the meeting to another room or time? ### Part 1 — Minimum number of rooms Implement `min_rooms(meetings) -> int`: the fewest rooms that can host every meeting so that no room ever holds two overlapping meetings. ```hint Watch the clock Think about how many meetings are running at each moment, and which moments are the only ones worth examining. ``` #### What This Part Should Cover - An O(n log n) algorithm, with an argument that its answer is both necessary and sufficient - Correct handling of a meeting that starts exactly when another ends - Time and space complexity ### Part 2 — Merge overlapping meetings The meetings have different start and end times and may partially overlap, nest inside one another or chain together. Implement `merge_meetings(meetings) -> list[list[int]]`, returning the disjoint blocks of time during which at least one meeting is running, sorted by start. ```hint Choose the visiting order Pick an order in which to visit the meetings so that each new one can only touch the block you are currently building. ``` #### What This Part Should Cover - Correct results for nested, chained and back-to-back meetings - The ordering the algorithm relies on, and why one pass is then enough - Complexity, and whether the caller's list is modified ### Part 3 — Handle conflicts Two meetings conflict when their time ranges overlap. Show how to detect conflicts in two situations: a new request checked against the meetings already booked in a room, and every conflicting pair within a list of meetings. Then explain how you would handle a request that conflicts. ```hint Keep bookings searchable For a single request, decide how the existing bookings should be stored so that you only look at the few that could possibly overlap it. ``` #### Clarifying Questions for this Part - Is there one room or several, and may a conflicting request be placed in a different room? - Should a rejected request come back with the meetings it conflicts with, or with the next free slot of the same length? #### What This Part Should Cover - A correct overlap test for two meetings, including shared endpoints - Efficient detection for one new request and for all conflicting pairs, with complexity - At least two ways to handle a conflicting request and the data each one needs ### What a Strong Answer Covers - Settles the endpoint convention, the input size and the batch-versus-online question before coding - Algorithms for counting rooms and for merging, each with a correctness argument and its complexity - One consistent endpoint convention across all three Parts - Tests for an empty list, a single meeting, identical meetings, nested meetings and back-to-back meetings - A clear explanation of the approach before and during coding ### Follow-up Questions - Return not only the number of rooms but also which room each meeting is assigned to. - Booking requests arrive one at a time throughout the day. How do you answer each one in O(log n)? - Meetings now carry priorities, and a higher-priority request may displace a lower-priority booking. What changes? - Given several people's calendars, find the earliest slot of a given length when all of them are free.