Lossless repacking of airline schedules

How a compact schedule representation creates an equivalence-class problem, and how we repack fragmented schedules into minimal form — with a guarantee we never lose a single operating date.
Part 2. Conflict detection in airline schedules
Part 3. Comparator contract violations in aircraft stand sorting

---

The representation

Airlines don't publish their schedules as lists of dates. A flight that operates every Monday, Wednesday and Friday all summer is one line, not ninety:

XX123  KZN → MAD   01JUN–30SEP   1.3.5..

That last field is a weekday mask in the IATA convention — digits 1–7 for Monday through Sunday, dots for days the flight doesn't operate. 1.3.5.. reads: Mondays, Wednesdays, Fridays.

The whole industry runs on this. SSIM files, slot-coordination telegrams, airport capacity systems — everywhere a repeating flight appears, it appears as a (validity period, weekday mask) pair. It's compact, humans can read it, and a season's schedule fits on a screen.

I work on an airport slot coordination platform — the system through which airlines request arrival and departure slots and airports allocate them. Our schedule rows use exactly this representation. And it has a property that looks harmless and isn't:

The same set of operating dates has many valid representations.

These three schedules are the same flight:

A:  01JUN–30JUN  1.3.5..   B:01JUN–15JUN  1.3.5..  C:01JUN–30JUN  1......
                             16JUN–30JUN  1.3.5..    01JUN–30JUN  ..3....
                                                     01JUN–30JUN  ....5..

Expand any of them to concrete dates and you get the identical set. A is one row. B is two. C is three. Operationally they are indistinguishable — and that's the problem.

How schedules fragment

Nobody writes version C on purpose. It emerges.

A coordinator moves the Friday departure time for two weeks in July: the edit has to split the row, because the change applies to a sub-range of the period and one day of the mask. An airline cancels three specific dates: more splits. A season of ordinary edits later, a flight that is conceptually "Mon/Wed/Fri all summer" is stored as a dozen slivers — short periods, sparse masks, some of them describing a single date in period-and-mask costume.

And this is not a per-flight issue — it compounds across the whole schedule. A season schedule is hundreds of flights, and ours runs to more than 300,000 rows before repacking. The repacker works group by group — rows are keyed by flight number and leg, and each group's operating dates are an independent equivalence-class problem — but the payoff sums over the collection: at the ~40% reduction we measured on production schedules, that's over a hundred thousand rows of pure representational debris removed, with not one operating date touched.

Fragmentation isn't just untidy:

• Humans read these rows. A slot coordinator scanning a fragmented schedule can't see the shape of the operation. Twelve slivers hide the pattern that one row states plainly.
• Everything downstream iterates over rows. Conflict detection, telegram generation, schedule comparison — all of it scales with row count, and much of it is worse than linear. Our conflict detection was O(n²) before we replaced it — fragmentation was directly inflating the n. (A story for another day)
• Comparisons produce false differences. Diffing an incoming schedule against a stored one when their periods don't share boundaries is its own hard problem — fragmentation multiplies it.

So we built a repacking operation: take a flight's rows, produce the minimal set of (period, mask) rows that generates exactly the same dates.

Why this is harder than "merge adjacent periods"

The naive instinct is interval merging — the classic coalesce-overlapping-ranges exercise. It fails here immediately, because rows interact across two dimensions that don't compose independently: the calendar axis and the weekday axis.

Two rows with identical masks and adjacent periods can merge along the period axis. Two rows with an identical period and different masks can merge along the mask axis (union the masks). But most real pairs are neither: they overlap partially in period and differ in mask, and merging them naively either invents dates that were never in the schedule or drops dates that were.

There's a subtler trap, too. A period–mask pair can encode dates that look different but generate the same set. 01JUN–30JUN ....5.. and 06JUN–27JUN ....5.. are the same Fridays — the first period's edges are slack, because June 1st isn't a Friday. Any correct algorithm has to reason about the generated date set, not about the period boundaries as written.

Which points at the only safe definition of equivalence:

Two schedule representations are equal if they expand to the same set of operating dates.

Everything else follows from taking that definition seriously.

The algorithm

Repacking runs as a pipeline: expand, deduplicate, then rebuild in three stages, cheapest structure first.

Stage 0 — expand and deduplicate

Expand every row to its concrete dates. Drop exact duplicates — rows whose entire date set is already covered by other rows contribute nothing and exist only as editing debris. What remains is the ground truth: one set of dates per flight number and leg (departure / arrival / return) — the unit whose rows describe the same operational data, and the only scope within which rows are ever combined.

From here on, the original rows are irrelevant. We rebuild from the dates.

Stage 1 — contiguous runs at a 7-day stride, per weekday

For each weekday independently, sort that weekday's dates and find maximal runs where consecutive dates are exactly 7 days apart. Each run becomes a candidate row: period = first to last date of the run, mask = that single weekday.

This stage alone converts "every Friday from June to September, except the two cancelled ones" into three tight single-weekday rows instead of a scatter of fragments. Crucially, the periods that come out of this stage are taut — they start and end on dates the flight actually operates, which eliminates the slack-boundary ambiguity by construction.

Stage 2 — the trivial merges first

The cheap cross-weekday case: candidate runs whose periods coincide exactly merge immediately into one row with the union of their masks. The Monday, Wednesday and Friday runs for the same June–September stretch collapse into a single 1.3.5.. row.

Stage 3 — greedy first-fit combination, tested for holes

What's left is the awkward remainder: runs that almost fit together. The final pass is greedy, first-fit: pick a column — one weekday's run — and walk the other runs until you find a partner that merges without holes. A proposed merge takes the union period (earliest start to latest end) and the union mask, expands the resulting row, and accepts it only if every date the merged (period, mask) implies is a real operating date — no holes in the implied grid, no phantom dates beyond the truth. First valid partner wins; repeat until no pair merges. The scan tries weekday-adjacent masks first.

The January flight in the examples below shows this pass earning its keep: the Monday run's concise period is 05JAN–09FEB and the Tuesday run's is 06JAN–03FEB — different boundaries, so no trivial merge — yet the union row 05JAN–09FEB 12..... implies exactly the real dates, and the merge stands.

The guard: every stage proves itself

Here is the part of the design I'd defend hardest.

After every stage, the pipeline expands its own output and compares the generated date set against the ground truth from Stage 0. Set equality, or the stage's result is rejected.

Set<LocalDate> truth = expand(originalRows);

List<Row> candidate = stage.apply(rows);
if (!expand(candidate).equals(truth)) {
    // this stage's optimisation is not lossless for this input —
    // reject it and continue with the previous representation
    candidate = rows;
}

And when no lossless packing exists for some residue of dates — irregular cancellations often leave one — there's a per-date fallback: those dates are emitted as single-date rows. Ugly, but correct, and correctness is not negotiable here. A schedule row in a slot coordination system is an airline's permission to land. An optimization that silently drops one Friday in August is not a performance bug; it's a plane with nowhere to go.

This guard is what let us ship aggressive optimization stages without fear. The greedy stage can be wrong about a merge — the guard catches it. A future maintainer can add a fourth stage with a subtle bug — the guard catches that too. The invariant is enforced structurally, not by hoping every stage is individually perfect.

Minimal-ish, provably lossless

Note what we did not build: an optimal minimiser. Finding the guaranteed-smallest set of (period, mask) rows is a set-cover-shaped problem, and greedy-with-verification gets ~40% row reduction on production schedules at a complexity a team can maintain. We chose absolute correctness and good-enough minimality over provable minimality — because the guard makes the first property certain, and nobody's operations depend on the second being perfect.

What it looks like in practice

Two anonymized examples — two flights out of the hundreds a single repack pass walks.

Example 1 — same row count, radically better rows. Three stored rows for one flight:

05JAN–26JAN  123...7
13JAN–02FEB  12...67
02FEB–09FEB  12...67

Thirty date-markings, but only 23 distinct dates — seven dates are covered twice, because the rows overlap in both period and mask (every Monday and Tuesday from 13JAN to 26JAN lives in two rows at once). The repack emits:

05JAN–09FEB  12.....
07JAN–21JAN  ..3....
11JAN–08FEB  .....67

Still three rows — but zero overlap, each period concise against its first and last operating date, and the operational shape (Mon/Tue core, Wednesdays for three weeks, weekends from mid-January) now readable at a glance. This is the case that taught us row count is the wrong success metric on its own: the real product is canonical, overlap-free form. Double-covered dates are quiet poison for anything downstream that counts, diffs or allocates by date.

Example 2 — a merge across misaligned boundaries, and the fallback. A different flight, three stored rows:

08DEC–22DEC  1......
13DEC–27DEC  .....6.
07DEC–07DEC  ......7

The Monday and Saturday runs have periods that share no boundary — 08–22 versus 13–27. This is exactly the shape that naive interval logic refuses to touch, and exactly where reasoning about generated dates instead of period edges pays off. Propose the merged row 08DEC–27DEC 1....6. and expand it: Mondays {8, 15, 22} — the 29th falls outside the period — and Saturdays {13, 20, 27}, with no phantom Saturday before the 13th because the first Saturday on or after the 8th is the 13th. The union period introduces no spurious dates; the guard's set-equality check confirms it; the merge stands. Three rows become two — not because the periods aligned, but because the dates did.

The Sunday, fitting no weekly pattern, passes through untouched as 07DEC–07DEC ......7 — a single-date row in period-and-mask costume. Inelegant, and exactly right: that Sunday is a real departure with a real slot, and no packing aesthetic is worth losing it. The fallback isn't an edge-case apology; it's the guard's promise made concrete.

One more design choice: repack as a diff, not a rewrite

The pipeline's output is not "delete everything, insert the new rows." It's a create/delete diff applied onto an undo/redo change stack — the same stack that holds a coordinator's manual edits.

Two things fall out of this. Repacking becomes an undoable action — a coordinator who dislikes the repacked shape presses Ctrl+Z, which matters more than you'd think for trust in an automated rewrite of their data. And the operation composes with concurrent editing instead of trampling it, because it goes through the same conflict-handling path as every human edit.

What I'd generalize from this

A compact representation is a contract with an equivalence class. The moment you choose (period, mask) over a date list, you accept that many encodings mean the same thing — and you will eventually need canonicalization, comparison, and a definition of equality over the meaning, not the encoding. Choose the representation anyway; just budget for the machinery.

Optimize greedily, verify absolutely. Where correctness is binary and the cost of silent loss is high, the winning structure is aggressive heuristics wrapped in a cheap total check. The heuristic can then be as clever or as sloppy as it likes — the guard converts "we believe each stage is right" into "the pipeline cannot emit a wrong answer, only a suboptimal one."

Make automated rewrites undoable. The cheapest way to get humans to trust an algorithm that rewrites their data is to let them un-do it with one key.

---

I build airport slot coordination and airline schedule systems — IATA telegram processing (SCR/SAL/SMA/SHL/SIR/WCR), schedule algorithms, conflict detection — in Java. Currently relocating to Spain. Find me on LinkedIn.