Find conflicting appointments
Problem
Appointments [start, end] arrive in order. Return every appointment that overlaps one that arrived before it, in arrival order. Two appointments that only touch (one ends exactly when the other starts) do not overlap.
Example 1
Input: [[1,5], [3,7], [2,6], [10,15], [5,6], [4,100]] Output: [[3,7], [2,6], [5,6], [4,100]]
[3,7] and [2,6] overlap [1,5]; [5,6] only touches [1,5] but overlaps [3,7]; [4,100] overlaps [1,5]. [10,15] overlaps nothing that came before it.
Also asked as: Given "n" appointments, find the conflicting appointments
Test cases
Case 1
Input: [[1,5],[3,7],[2,6],[10,15],[5,6],[4,100]] Expected: [[3,7],[2,6],[5,6],[4,100]]
Case 2
Input: [[1,10],[2,3],[4,5]] Expected: [[2,3],[4,5]]
Case 3
Input: [[5,6],[1,10]] Expected: [[1,10]]
Case 4
Input: [[1,2],[2,3]] Expected: []
Case 5
Input: [] Expected: []
View solutionHide solution1 approach
1. Interval tree (BST by start, each node stores its subtree’s max end)
Time O(n log n) on average, O(n²) if the tree degeneratesSpace O(n)
Keep the earlier appointments in a BST keyed by start, where every node also stores the largest end in its subtree. Before inserting a new appointment, search for an overlap: check the node, then go left only if the left subtree’s max end is after the new start, otherwise go right.
function conflictingAppointments(appts) { let root = null; const conflicts = []; // does any appointment in the tree overlap [s, e]? const overlaps = (node, s, e) => { while (node) { if (s < node.end && node.start < e) return true; // the left subtree can only overlap if one of its appointments ends after s node = node.left && node.left.max > s ? node.left : node.right; } return false; }; const insert = (node, s, e) => { if (!node) return { start: s, end: e, max: e, left: null, right: null }; if (s < node.start) node.left = insert(node.left, s, e); else node.right = insert(node.right, s, e); node.max = Math.max(node.max, e); return node; }; for (const [s, e] of appts) { if (overlaps(root, s, e)) conflicts.push([s, e]); root = insert(root, s, e); } return conflicts;}Sorting by start and sweeping finds overlaps too, but it loses the arrival order: it would report an appointment as conflicting with one that arrived after it.