# When Hours Collide > Two reservations, one slot. Find every clash. Canonical URL: Domain: Python · Difficulty: medium · Seniority: L5 ## Problem A shared room-booking calendar stores each reservation as a `[name, start, end]` record, and you need to flag every scheduling clash. Ranges are half-open [start, end), so a booking that ends exactly when another begins does not clash. Return each clashing pair once as `[name_a, name_b]` with the earlier-starting booking first, ordered by the first booking's start and then the second's, or an empty list when nothing clashes. ## Worked solution and explanation ### What this really is Strip the calendar costume and this is pairwise interval intersection with two traps that sink otherwise-correct code. First the boundary: the ranges are half-open, so `[9, 10)` and `[10, 12)` share the instant 10 but do NOT overlap. Write the test with `<=` and you flag every back-to-back booking as a clash, which is the one thing a scheduler must never do. Second the order: the input is not sorted, so if you emit pairs in the order the loop happens to find them, two clashes come back in the wrong sequence and exact-match grading fails even though you found every collision. The fix for both is small: a strict two-sided overlap test, each pair written earlier-booking-first, and a final sort of the collected pairs by start time. > **Trick to Solving** > > Each event is a list `[name, start, end]`, so unpack by index: `name, start, end = event`. Two ranges overlap only when `start_a < end_b` and `start_b < end_a`, both strict. Since the input arrives in no particular order, keep BOTH conditions and sort the pairs you collect rather than trusting loop order. --- ### Break down the requirements #### Step 1: Check every pair once Walk every pair with a nested loop where the inner index starts one past the outer (`j` from `i + 1`). That visits each unordered pair exactly once, so a clash is never reported twice. #### Step 2: Test for a real overlap Two ranges overlap only when `start_a < end_b` and `start_b < end_a`, both strict. Because the events are NOT pre-sorted, either one could start first, so you genuinely need both halves of the test: drop one and a reversed, non-touching pair sneaks through as a false clash. A shared boundary fails the strict test, which is exactly what half-open ranges demand. #### Step 3: Order the pairs Write each surviving pair with the earlier-starting booking first, and stash its two start times alongside the names. The loop groups one event's pairs together, which is NOT the promised output order, so sort the collected pairs by (first start, second start) at the end. That final sort is what turns a correct set of clashes into the exact sequence the grader wants. --- ### The solution **All-pairs half-open overlap detection** ```python def find_overlaps(events: list[list]) -> list[list[str]]: collisions = [] for i in range(len(events)): name_a, start_a, end_a = events[i] for j in range(i + 1, len(events)): name_b, start_b, end_b = events[j] if start_a >= end_b or start_b >= end_a: continue if start_a <= start_b: collisions.append((start_a, start_b, name_a, name_b)) else: collisions.append((start_b, start_a, name_b, name_a)) collisions.sort(key=lambda c: (c[0], c[1])) return [[name_a, name_b] for _, _, name_a, name_b in collisions] ``` > **Time and Space Complexity** > > **Time:** O(n^2 + p log p), where p is the number of pairs returned. Every pair is compared once (O(n^2)), and the collected pairs are sorted once (O(p log p)). > > **Space:** O(p) for the collected and returned pairs. > **Interviewers Watch For** > > Whether you keep BOTH halves of the overlap test. Candidates who mentally pre-sort the events drop to a one-sided `start_b < end_a` and it passes the friendly cases, then breaks the moment a later-listed booking actually starts earlier. Naming why both halves are needed on unsorted input signals you reasoned about the data, not just the happy path. > **Common Pitfall** > > Three ways to lose otherwise-correct code: using `<=` instead of `<` (the ranges are half-open, so a boundary touch is not a clash); trusting the loop's emission order instead of sorting the collected pairs; and unpacking each event as a dict when it is a plain list, so it is index in, not key. --- ## Common follow-up questions - How would you find the maximum number of simultaneous overlapping events? _(Tests sweep-line algorithm with event start/end point sorting.)_ - What if events are added in a stream? _(Tests interval tree or segment tree for dynamic overlap queries.)_ - How would you resolve conflicts automatically? _(Tests scheduling algorithms like greedy interval scheduling.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/when_hours_collide) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.