Second post about the algorithms inside an airport slot coordination platform. The first one was about repacking schedules into canonical form. This one is about the question a coordinator asks right after: which of these rows are fighting over the same slot?
Part 3. Comparator contract violations in aircraft stand sorting
The setup
An airport slot coordination system stores schedules as rows of (validity period + weekday mask) — a compact representation whose care and feeding I covered last time. A season schedule runs to hundreds of flights and, in our production system, 300,000+ rows. Rows arrive from several directions at once — coordination telegrams, draft edits, imports — and sometimes the schedule ends up with rows of the same flight whose operating dates collide: the same flight identity holding competing claims for a date. That's a conflict — and note it's strictly a same-flight affair; in this model, two different flights cannot conflict with each other.
A coordinator can't act on a schedule in that state. The system's job is to find every such situation across the whole collection and show it — fast enough to run interactively, on every check.
Why the obvious answer is wrong twice
The obvious answer is to compare every row with every other — and I don't have to speculate about how that goes, because that's what the check did when I met it. On a 14,799-row collection, all-pairs is
14,799 × 14,798 / 2 ≈ 109 million comparisons
— each involving date-range expansion. Across the full 300,000-row production schedule, the same shape reaches ~45 billion. In practice the check ran for about 20 seconds. I watched that spinner, did this arithmetic, and decided the algorithm didn't deserve its runtime.
Twenty seconds is the first "wrong": quadratic cost on a collection that, as the previous article showed, is inflated by representational fragmentation to begin with. Fragmentation and pairwise comparison compound each other — every unnecessary sliver multiplies against every other row.
The second "wrong" is subtler and more interesting: pairs are the wrong output shape. If row A collides with row B, and B collides with C, that is not two findings — it's one conflict involving three rows, and the coordinator needs to see it whole to resolve it. Conflict is a transitive, relational property. A list of pairs pushes the grouping work onto the user's eyeballs.
Conflicts are groups, not pairs. What we're really computing is the connected components of a collision relation.
Idea one: never compare strangers
The definition above does half the work for us: conflicts are same-flight by construction, so rows belonging to different flights never need to be compared at all. Before any date is expanded, partition the collection by flight identity — airline and flight number.
One linear pass with a hash map, and the one huge n² shatters into thousands of tiny problems — most clusters holding a handful of rows. This is where the 45 billion goes to die: almost every pair the naive version compared was a pair that could never conflict.
One wrinkle: a schedule row in a slot system describes a turnaround — an arrival leg and a departure leg, each with its own flight identity. So a single row participates in two clusterings, once by its arrival identity and once by its departure identity. Hold that thought; it's where the output gets its precision.
Idea two: groups are connected components
Within each cluster, expand rows to their operating dates. Two rows collide when they share a date. And because we want groups, not pairs, we don't record collisions — we merge them, with a Union-Find — also known as a disjoint-set union, DSU — the textbook structure for "who's in the same group":
final class UnionFind {
private final int[] parent;
private final int[] rank;
UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
void union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
if (rank[ra] < rank[rb]) parent[ra] = rb; // smaller tree under bigger
else if (rank[ra] > rank[rb]) parent[rb] = ra;
else { parent[rb] = ra; rank[ra]++; }
}
}
Mine used union by rank — always hang the shallower tree under the deeper root, which bounds find at O(log n). The textbook goes further: add path compression and the amortized cost drops to inverse-Ackermann, i.e. effectively constant. I didn't bother, and that's a deliberate point, not a confession: after the identity partition, each cluster holds a handful of rows, and log of a handful is nothing. The asymptotic profile of the union structure never showed up in a profiler — the clustering had already done the heavy lifting. Optimizing the Union-Find further would have been polishing the doorknob on a door we'd already removed.
The mechanics within a cluster: walk each row's dates, keep a map from date to the first row seen on that date; when a second row lands on an occupied date, union the two rows. At the end, every disjoint set with more than one member is one conflict group — the A–B–C chain falls out for free:
Row A: 01JUN–30JUN 1...... (Mondays, all June)
Row B: 15JUN–15JUL 1...... (Mondays, mid-June to mid-July)
Row C: 01JUL–31JUL 1...... (Mondays, all July)
A and C never share a date. But A–B collide in late June, B–C collide in early July — so union chains all three into one component. One conflict, three rows, exactly what the coordinator must see to fix it. A pairwise report would have shown two separate findings and left the user to discover they're one problem.
The output: not just "conflict", but which leg
Because each row was clustered twice — by arrival identity and by departure identity — the result can say which side of the turnaround is at fault. Each row gets marked arrival-conflicted, departure-conflicted, or both (a row whose arrival leg collides in one cluster and whose departure leg collides in another carries both flags), plus a total conflict count for the collection. The UI highlights the exact leg, not just the row.
That leg-level precision is the difference between an alarm and a diagnosis. "This row is in conflict" sends the coordinator hunting; "this row's departure is double-claimed on 12 dates" tells them where to cut.
What it costs now
Two passes, each effectively linear: one hash-map partition over all rows, then per-cluster date walks with cheap unions.
Before: ~20 seconds for the check across the production schedule — a spinner, a context switch, a thing you schedule around.
After: a 14,799-row collection checks in 20 ms — a keystroke.
Fast enough that conflict detection stopped being a batch job you schedule and became a property of the schedule you simply always see.
Wait — didn't the repacking article make this problem disappear?
Fair question, if you read the previous post: if schedules get canonicalized into overlap-free form, what's left to detect?
The two algorithms treat different diseases. A repacked row carries exactly one operational payload — one departure time, one aircraft, one set of business fields — so repacking can only merge rows that agree on everything except how their dates are written. It removes redundant duplication: the same claim, encoded messily. But two rows of the same flight with different payloads on colliding dates are not redundancy — they're contradiction. The canonical example from our production data: the same flight number claiming two different airports on the same date. A plane cannot land in two cities at once, and no algorithm should resolve that by silently picking a winner — deciding which claim is true is the coordinator's job. (Milder versions abound: same flight, same date, different departure times, different aircraft.) Repacking is forbidden to touch that pair, so it survives canonicalization — and surfacing it, whole and precisely blamed, is what conflict detection is for.
Tidy the redundancy automatically; hand the contradictions to a human. The boundary between those two is the most important line in the whole system. And it compounds with the repacking from article #1: canonical schedules keep n small; near-linear detection keeps the check cheap at any n. The two algorithms are one story — representation hygiene and cheap verification, feeding each other.
What I'd generalize
Name the output shape before choosing the algorithm. The naive version wasn't slow because pairwise comparison is slow — it was slow because pairs were never the answer. The moment the requirement was stated as "groups", the structure (connected components, Union-Find) was inevitable. Most O(n²) scans hiding in business systems are really badly-shaped questions.
Partition by identity before comparing by value. The two-level shape — coarse hash partition on an identity key, fine relational pass within each bucket — turns quadratic problems near-linear whenever most pairs can be excluded by a cheap key. It's the same trick as a hash join, wearing domain clothes.
Precision of blame is a feature. Clustering each row twice (per leg) cost almost nothing and turned the output from "something's wrong here" into "cut this leg on these dates". The cheapest UX win in the whole system came from the algorithm's bookkeeping, not the UI.
I build airport slot coordination and airline schedule systems — IATA telegram processing, schedule algorithms, conflict detection — in Java. Currently relocating to Spain. The previous post in this series: lossless repacking of airline schedules. Find me on LinkedIn.
Top comments (0)