437. Find All Conflicting Appointments

Given n appointments, each with a start and end time, find every appointment that overlaps with at least one appointment that came before it in the input order (two appointments [s1,e1) and [s2,e2) overlap when s1 < e2 and s2 < e1). Print each conflicting appointment, in input order, as 'start end' on its own line; if none conflict, print 'None'. The first line has n; each of the next n lines has one appointment's start and end.

Input: First line contains the integer n. Each of the next n lines contains two integers - an appointment's start and end time. Output: Print each conflicting appointment as 'start end' on its own line, in input order, or print 'None' if none conflict.

1 <= n <= 10^4

An appointment only needs to be reported ONCE, the moment any single conflict with an earlier appointment is found - there's no need to enumerate every conflicting pair for it once its own conflicting status is already established.

Given a list of appointments in the order they were booked, find every appointment that overlaps with some EARLIER appointment. Brute force: For every new appointment, compare it against ALL previously-inserted appointments directly - this costs O(n²) in the worst case, too slow for larger appointment lists. Optimised: Storing appointments in a BST ordered by start time (or an interval-tree variant that also tracks each subtree's maximum end time) lets you PRUNE large portions of the search when checking for overlaps - since a plain overlap check against every single earlier appointment is still worst-case O(n) per new one without the BST's pruning power, but with careful augmented tracking, checks can be done much faster than brute force on average.

Process appointments in input order, and for each one compare it directly against every appointment that came before it using the overlap test s1 < e2 and s2 < e1, marking it as conflicting the moment any earlier appointment overlaps it. This is a direct translation of the problem statement so it is trivially correct, but comparing every appointment against all of its predecessors means the work grows quadratically as more appointments are processed. Time: O(n^2) Space: O(1)

Coordinate-compress all start times into ranks, and maintain a Fenwick tree (Binary Indexed Tree) indexed by that rank which supports a prefix-maximum query: 'what is the largest end time seen so far among appointments whose start is less than X'. Process appointments strictly in input order: for each one, binary search for the rank boundary corresponding to its end time, query the Fenwick tree for the maximum end time among earlier appointments with a smaller start, and if that maximum end exceeds the current start, it conflicts; then insert this appointment's end time at its own rank. Because each query and update touches only O(log n) Fenwick tree nodes instead of scanning a list, the whole process runs in guaranteed O(n log n) time regardless of input order. Time: O(n log n) Space: O(n)

Maintain the previously processed appointments in an array kept sorted by start time (inserting each new one at its correct position, e.g. via binary search plus a shift). For each new appointment, binary search to jump straight to the earliest previous start time that could possibly still be unmatched and only scan forward through starts that are less than the new appointment's end time, stopping as soon as starts exceed it. This prunes away many of the comparisons brute force would make against clearly non-overlapping appointments, though a pathological ordering can still force it back toward quadratic behavior. Time: O(n^2) worst case, much better in practice Space: O(n)

1. Insert appointments one at a time (in their given order) into a BST ordered by start time. 2. BEFORE inserting each new appointment, check it against the appointments already in the tree for an overlap - an appointment [s,e) overlaps an existing [s2,e2) exactly when s < e2 and s2 < e. 3. If any overlap is found, report the new appointment as conflicting - one conflict found is enough, no need to check every existing appointment once a conflict is confirmed. 4. Insert the new appointment into the tree regardless, so future appointments can be checked against it too.

Time: O(n log n) on average with a balanced BST-based overlap check per appointment, though a naive BST search alone doesn't guarantee this without additional augmentation (like tracking subtree max-end-time) for full interval-tree-style efficiency. Space: O(n), for the BST holding all inserted appointments.

Test with n=1 (no conflict possible, print 'None'), appointments that touch but don't overlap (one's end equals another's start, which the strict inequality excludes), fully nested or identical intervals, and n=10^4 for performance.

Be ready to mention that a proper INTERVAL TREE (a BST augmented with each subtree's maximum end time) is the fully rigorous data structure for this class of problem, guaranteeing efficient overlap queries even in adversarial cases - a strong signal if brought up proactively.