Given n appointments, find the conflicting appointments

The problem, simply

You get n appointments in the order they were booked. Each has a start time and an end time. For every appointment, find an earlier booked appointment that it clashes with, if there is one.

Two appointments clash when they overlap: a.start < b.end and b.start < a.end. One ending exactly when the other starts is not a clash.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each appointment, look at every earlier one.

1. For i from 1 to n - 1, and for every j < i:
2. If a[j] and a[i] overlap, report a[i] clashes with a[j] and stop looking for this i.

import java.util.*;

class Solution {
    // returns, for each booking, the index of an earlier clashing booking, or -1
    public int[] findConflicts(int[][] appts) {
        int n = appts.length;
        int[] clash = new int[n];
        Arrays.fill(clash, -1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (appts[j][0] < appts[i][1] && appts[i][0] < appts[j][1]) {
                    clash[i] = j;              // first earlier booking that overlaps
                    break;
                }
            }
        }
        return clash;
    }
}

How long it takes: up to n * n / 2 checks, O(n^2). Extra room besides the answer: O(1).

Way 2: the clever way

Keep the earlier bookings in a BST filed by start time, where every spot also stores max: the latest end time in its part of the tree. This is called an interval tree.

To check a new booking [s, e], walk down from the top:

1. If the current spot's booking overlaps [s, e], report it.
2. Else, if the left child exists and its max > s, go left. Something on the left still runs after s starts.
3. Else go right. Everything on the left ends by s, so none of it can clash.

Then insert [s, e] like a normal BST insert by start, and raise max on every spot along the way.

Why going left is safe: if the left side's max > s but nothing there overlaps, then the booking with that late end must start at or after e. Everything on the right starts even later, so the right side cannot overlap either.

import java.util.*;

class Solution {
    static class Spot {
        int start, end, max, index;            // max: latest end in my part of the tree
        Spot left, right;
        Spot(int s, int e, int i) { start = s; end = e; max = e; index = i; }
    }

    public int[] findConflicts(int[][] appts) {
        int[] clash = new int[appts.length];
        Spot root = null;
        for (int i = 0; i < appts.length; i++) {
            Spot hit = overlap(root, appts[i][0], appts[i][1]);
            clash[i] = (hit == null) ? -1 : hit.index;
            root = insert(root, appts[i][0], appts[i][1], i);
        }
        return clash;
    }

    private Spot overlap(Spot node, int s, int e) {
        while (node != null) {
            if (node.start < e && s < node.end) return node;          // clash here
            if (node.left != null && node.left.max > s) node = node.left; // left still runs after s
            else node = node.right;                                      // left is all over by s
        }
        return null;
    }

    private Spot insert(Spot node, int s, int e, int i) {
        if (node == null) return new Spot(s, e, i);
        if (s < node.start) node.left = insert(node.left, s, e, i);
        else node.right = insert(node.right, s, e, i);
        node.max = Math.max(node.max, e);                                // keep max up to date
        return node;
    }
}

How long it takes: each booking walks one road to check and one road to insert, O(h), so O(n h) in total. With a self balancing tree, h stays about log n, which gives O(n log n). With a plain BST and bookings that arrive sorted by start, the tree becomes a stick and it drops to O(n^2). Extra room: one spot per booking, O(n).

Watch out for

• Touching is not overlapping here. Use strict < in both parts of the check. If the problem says touching counts, change both to <=.
• Forgetting to raise max on the way down during insert. Then the left or right choice is made with stale numbers.
• This finds one clash per booking, not all of them. Listing all clashes needs to search both sides when both can hold overlaps, which costs O(h + k) for k answers.

What interviewers ask next

• Can a person attend all meetings (LeetCode 252)? Sort by start and check each pair of neighbors. O(n log n).
• Book a calendar online, refusing clashes (LeetCode 729). Use a TreeMap from start to end: check the booking just before (floorKey) and just after (ceilingKey). O(log n) per booking.
• List every clashing pair. Sort by start, then sweep, keeping a min heap of end times of bookings still running. Each new booking clashes with everyone in the heap whose end is after its start. O(n log n + k).
• How many rooms are needed (LeetCode 253)? Sweep starts and ends in time order. The most bookings running at once is the answer.

Remember this

Grown-up words: the notebook is an interval tree (a BST augmented with the max end of each subtree), a clash is an interval overlap, walking one road is an O(h) search, and keeping max correct during insert is maintaining the augmentation.