Airport gate assignment

An airport has a set of gates. Flights arrive and depart at known times, and each flight needs a gate for the time it sits at the airport. Assign flights to gates so that no two flights overlap on one gate, large aircraft only use gates that fit them, and as many flights as possible get a gate. When a flight is delayed, the plan must adjust. Unlike the earlier problems, the interesting part here is an algorithm, not only a structure.

• Each flight has an id, an aircraft size, an arrival time and a departure time.
• Each gate has an id and the largest size it can handle.
• A flight may use a gate of its size or larger.
• Two flights on the same gate must be separated by a buffer (for cleaning and boarding), say 20 minutes.
• If no gate fits, the flight is reported as unassigned, not silently dropped.
• Delays and cancellations arrive during the day and may force reassignment.
• Out of scope: baggage, crew, taxi routes between runway and gate.

Each flight occupies a time interval from arrival to departure plus the buffer. Two flights conflict if their intervals overlap. The question is a classic one called interval partitioning: split intervals into the fewest groups where nothing inside a group overlaps. Each group is one gate.

The key fact: the minimum number of gates needed equals the maximum number of flights present at the same moment. You cannot do better than the busiest instant, and a simple greedy method achieves it.

Sort flights by arrival time. Keep a min-heap of the times when each used gate becomes free. For each flight, if the earliest-free gate is free by the flight's arrival, reuse it. Otherwise open a new gate.

function gatesNeeded(flights: Flight[], buffer: number): number {
  const sorted = [...flights].sort((a, b) => a.arrive - b.arrive);
  const free = new MinHeap<number>((a, b) => a - b);   // times gates become free
  for (const f of sorted) {
    if (free.size > 0 && free.peek() + buffer <= f.arrive) free.pop();
    free.push(f.depart);
  }
  return free.size;
}

Sorting costs O(n log n) and each heap operation O(log n), so the whole thing is O(n log n). After the loop the heap holds one entry per gate, so its size is the answer. Greedy is provably optimal here because processing by earliest arrival never wastes a gate that could have been reused.

Our airport has a fixed set of gates, not an unlimited supply, and gates have sizes. Two things follow.

• The goal changes from "fewest gates" to "most flights assigned", and some flights may have to be rejected.
• Size compatibility splits flights into classes. A large aircraft can use only large gates, while a small one can use any. With such restrictions the greedy method is no longer guaranteed optimal, and the general problem becomes much harder (it is related to graph coloring, which is hard in general). A good heuristic is the practical choice.

Best fit is a sound heuristic: among gates that are free and big enough, choose the smallest one. This keeps large gates open for large aircraft that may arrive later, which is exactly the resource that is scarce.

• Flight: a value with id, size, arrival and departure.
• Gate: owns its own calendar of bookings and can answer "can you take this flight?" By Information Expert, the gate knows its bookings.
• GateAssigner: a strategy that chooses a gate for a flight. First fit, best fit and "closest to the terminal" are different assigners.
• Scheduler: the coordinator that holds the gates, runs the assigner, and records assignments.

enum Size { Small, Medium, Large }
type Flight = { id: string; size: Size; arrive: number; depart: number };

class Gate {
  private bookings: Flight[] = [];                 // kept sorted by arrival
  constructor(readonly id: string, readonly size: Size) {}

  canTake(f: Flight, buffer: number): boolean {
    if (this.size < f.size) return false;
    return this.bookings.every(
      (b) => f.depart + buffer <= b.arrive || b.depart + buffer <= f.arrive,
    );
  }
  add(f: Flight) {
    this.bookings.push(f);
    this.bookings.sort((a, b) => a.arrive - b.arrive);
  }
  remove(id: string) { this.bookings = this.bookings.filter((b) => b.id !== id); }
}

interface GateAssigner { choose(f: Flight, gates: Gate[], buffer: number): Gate | null }

class BestFit implements GateAssigner {
  choose(f: Flight, gates: Gate[], buffer: number) {
    const fits = gates.filter((g) => g.canTake(f, buffer));
    fits.sort((a, b) => a.size - b.size);          // smallest sufficient gate first
    return fits[0] ?? null;
  }
}

class Scheduler {
  private where = new Map<string, Gate>();
  constructor(private gates: Gate[], private assigner: GateAssigner, private buffer = 20 * 60000) {}
  assign(f: Flight): Gate | null {
    const g = this.assigner.choose(f, this.gates, this.buffer);
    if (g) { g.add(f); this.where.set(f.id, g); }
    return g;                                       // null means unassigned
  }
  cancel(id: string) { this.where.get(id)?.remove(id); this.where.delete(id); }
}

The overlap test is two simple comparisons: flight A fits before B if A's departure plus the buffer is no later than B's arrival, or the other way round. The every scan is O(k) for a gate with k bookings. A gate with many bookings could keep them sorted and use binary search to find the neighbors only, which is O(log k).

A delay changes a flight's interval and may now overlap the next booking. Three reasonable policies:

• Keep the gate if it still fits: update the interval and check canTake against the other bookings.
• Move the delayed flight to another gate that is free for the new interval.
• Bump a later flight that now conflicts, and try to place it elsewhere.

Prefer the smallest change, since moving flights means moving passengers. A delay is naturally published as an event, FlightDelayed, so the scheduler, the display boards and the ground crew each react independently. To keep the schedule consistent, make the change atomic: remove, check and re-add under one lock, so a half-updated calendar is never visible. If reassignment fails, report a conflict for a person to resolve rather than hiding it.

• Two flights with a gap larger than the buffer share one gate. With a smaller gap they do not.
• A large aircraft is never given a small gate.
• Best fit leaves the large gate open for a later large flight.
• When all suitable gates are busy the flight is returned as unassigned.
• Cancelling frees the slot for a new flight.
• A delay that creates an overlap triggers a reassignment or a reported conflict.
• The gatesNeeded function returns the maximum overlap on a hand-made example.

Use fixed integer times, so tests are exact and need no real clock.

• Walking distance: add a cost to each gate and choose the cheapest fit, which is a new assigner.
• Airline preferences or terminals: constraints on canTake, kept as small composable rules.
• Optimal assignment: for a quiet night, an offline search or an optimizer may beat the greedy result. Keep the GateAssigner interface so it can be swapped in.
• Several airports: one scheduler per airport behind a repository.

• Forgetting the buffer, so back-to-back flights are rejected or, worse, accepted too tightly.
• Treating intervals as closed on both ends, which makes touching times conflict.
• Hard-coding the choice of gate inside the scheduler instead of a strategy.
• Hiding unassigned flights, instead of reporting them.
• Recomputing the whole day for one delay when a local fix would do.