Detecting Overlapping Duty Segments in Python

The exact task this guide solves is finding duty segments that overlap in time for the same crew member — a double-booked leg, a positioning segment that runs into a flight, a duplicated event from two feeds — before those overlaps silently corrupt every downstream duration. Overlapping segments are the most common data-quality failure in an ingested roster, and they are insidious: a rule engine that sums segment durations will double-count the overlap, inflating flight time and shrinking rest, so a pairing that is actually illegal can pass and one that is legal can be rejected. This page detects overlaps with a linear sweep-line pass and with PostgreSQL range operators, and reports the offending pair. It hardens the flight time calculation algorithms against bad input and complements the validation done at flight data ingestion.

Prerequisites

Python 3.11+ with timezone-aware datetime.
Segments with UTC start and end instants and a crew identifier.
Half-open interval convention — a segment covers [start, end), so touching endpoints do not count as an overlap.
PostgreSQL 14+ with tstzrange for the set-based path.

Why overlap detection comes before any duration math

An overlap means two segments claim the same slice of a crew member’s time, which is physically impossible and always a data error. If the sweep that sums flight or duty minutes runs before overlaps are removed, the overlapping minutes are counted twice, so the very first correctness property a flight-time engine needs is that no two segments for one crew member overlap. Detecting overlaps is therefore a gate, not a report: a roster with overlaps is rejected or quarantined, not evaluated.

Step 1 — Detect overlaps with a sweep line

Sorting the segments by start instant lets a single pass find every overlap: two segments overlap exactly when the next one starts before the current maximum end. Tracking the running maximum end and the segment that set it makes the reported pair actionable.

from dataclasses import dataclass
from datetime import datetime


@dataclass(frozen=True, slots=True)
class Segment:
    segment_id: str
    start_utc: datetime
    end_utc: datetime


def find_overlaps(segments: list[Segment]) -> list[tuple[str, str]]:
    """Return (earlier_id, later_id) pairs whose [start, end) intervals overlap."""
    ordered = sorted(segments, key=lambda s: s.start_utc)
    overlaps = []
    active = ordered[0] if ordered else None
    for seg in ordered[1:]:
        if seg.start_utc < active.end_utc:          # strictly before → overlap
            overlaps.append((active.segment_id, seg.segment_id))
            # Keep whichever reaches furthest, so a chain of overlaps is all caught.
            if seg.end_utc > active.end_utc:
                active = seg
        else:
            active = seg
    return overlaps

Verify: for segments A [08:00,10:00), B [09:30,11:00), C [11:00,12:00), find_overlaps returns [("A", "B")] — A and B overlap by 30 minutes, while C starts exactly when B ends and, under the half-open convention, does not overlap.

Step 2 — Distinguish an overlap from an exact duplicate

Two feeds delivering the same segment produce an overlap that is really a duplicate, and the remedy differs: a duplicate is deduplicated, a genuine overlap is escalated to a scheduler. Comparing the intervals for equality separates the two.

def classify_overlap(a: Segment, b: Segment) -> str:
    if a.start_utc == b.start_utc and a.end_utc == b.end_utc:
        return "duplicate"          # same interval from two sources → dedupe
    return "conflict"               # genuine double-booking → escalate

Verify: two segments with identical start and end classify as duplicate; a segment that merely straddles another classifies as conflict, so the pipeline dedupes the first and quarantines the second.

Step 3 — Detect overlaps in the database

When the roster already lives in PostgreSQL, a self-join on tstzrange overlap finds every conflicting pair in one statement, and a GiST index on the range keeps it fast for large crews.

SELECT a.segment_id AS earlier, b.segment_id AS later
FROM duty_segment AS a
JOIN duty_segment AS b
  ON a.crew_id = b.crew_id
 AND a.segment_id < b.segment_id
 AND tstzrange(a.start_utc, a.end_utc, '[)') && tstzrange(b.start_utc, b.end_utc, '[)');

The && operator is the range overlap test, and '[)' makes the ranges half-open so touching endpoints do not register. The a.segment_id < b.segment_id clause reports each pair once rather than twice.

The sweep line flags A and B, which share the 09:30–10:00 slice; C starts exactly when B ends and, under the half-open convention, is a clean hand-off rather than an overlap.

Failure modes and troubleshooting

Closed intervals treated as overlaps. With closed intervals, a segment ending at 11:00 and one starting at 11:00 falsely overlap. Remediation: use half-open [start, end) intervals everywhere.
Duplicates escalated as conflicts. Treating a two-feed duplicate as a scheduling conflict floods schedulers with false alarms. Remediation: classify identical intervals as duplicates and dedupe them.
Only adjacent pairs checked. Comparing each segment to just its immediate neighbour misses a short segment fully contained in a long one. Remediation: track the running maximum end so containment is caught.
Local-time sort. Sorting by local time lets a date-line crossing reorder segments and hide an overlap. Remediation: sort and compare on UTC instants.
Summing before gating. Running the flight-time sum before overlap detection double-counts the overlap. Remediation: gate on overlap detection first; quarantine the roster on any conflict.

Frequently Asked Questions

Why are half-open intervals important here?

Because back-to-back segments are normal and legal — one duty ends exactly as the next begins. Half-open intervals [start, end) treat a shared endpoint as a clean hand-off rather than an overlap, so the detector does not flag every legitimate connection.

Flight Time Calculation Algorithms — the parent section whose sums depend on clean, non-overlapping segments.
Handling UTC and DST Edge Cases in Flight Time Math — the sibling temporal-correctness check.
Flight Data Ingestion & System Sync — where duplicate and conflicting segments enter the pipeline.
Data Schema Validation Rules — the boundary that rejects malformed segments.

Back to Flight Time Calculation Algorithms.