Build Lab and Consultation Appointment Matches

Problem Statement

You are building a scheduling service for a clinic that offers combined diagnostic visits. Patients need to book two consecutive appointments: first a "lab" visit, followed by a "consultation" visit.

You are given a list of raw provider availability records. Your task is to process these records into bookable 30-minute appointment options and find all valid pairs of lab and consultation appointments.

Pipeline Steps

1. Validation & Filtering:

   • Each record is a dictionary: {"provider_id": str, "type": str, "start": str, "end": str} where times are in "HH:MM" 24-hour format.
   • Valid records must have type as either "lab" or "consultation".
   • Each record must represent exactly a 10-minute block (end - start == 10 minutes), and both start and end minutes must align to 10-minute boundaries (e.g., minute values must be multiples of 10: 00, 10, 20, 30, 40, 50).
   • Ignore any records that do not meet these criteria. Discard duplicate identical slots for the same provider.

2. Merge Contiguous Slots:

   • Group valid records by provider_id and type.
   • Merge any overlapping or back-to-back 10-minute intervals into maximal continuous availability windows.

3. Generate 30-Minute Appointments:

   • Each appointment must be exactly 30 minutes long.
   • From each merged continuous window, generate all possible 30-minute appointments starting at 10-minute step increments (e.g., a window from 09:00 to 09:40 yields appointments 09:00-09:30 and 09:10-09:40).

4. Find Valid Lab-Consultation Pairs:

   • Pair every generated "lab" appointment with every generated "consultation" appointment such that:
     • The consultation starts at or after the lab ends: consultation.start >= lab.end.
     • The wait time between them is at most 60 minutes: consultation.start - lab.end = lab.end).

Function Signature

def find_appointment_pairs(records: list[dict]) -> list[dict]:
    """
    Returns a list of paired appointments in the format:
    [
        {
            "lab": {"provider_id": str, "start": str, "end": str},
            "consultation": {"provider_id": str, "start": str, "end": str},
            "wait_minutes": int
        },
        ...
    ]
    Sorted primarily by lab start time, secondarily by consultation start time,
    and tertiarily by lab provider_id.
    """
    pass

Constraints

• 0 <= len(records) <= 2000
• Times fall within a single day (00:00 to 23:59).
• Times are valid "HH:MM" strings.

Examples

Example 1

records = [
    {"provider_id": "P1", "type": "lab", "start": "09:00", "end": "09:10"},
    {"provider_id": "P1", "type": "lab", "start": "09:10", "end": "09:20"},
    {"provider_id": "P1", "type": "lab", "start": "09:20", "end": "09:30"},
    {"provider_id": "P1", "type": "lab", "start": "09:30", "end": "09:40"},
    {"provider_id": "P2", "type": "consultation", "start": "10:00", "end": "10:10"},
    {"provider_id": "P2", "type": "consultation", "start": "10:10", "end": "10:20"},
    {"provider_id": "P2", "type": "consultation", "start": "10:20", "end": "10:30"},
]

Output:

[
    {
        "lab": {"provider_id": "P1", "start": "09:00", "end": "09:30"},
        "consultation": {"provider_id": "P2", "start": "10:00", "end": "10:30"},
        "wait_minutes": 30
    },
    {
        "lab": {"provider_id": "P1", "start": "09:10", "end": "09:40"},
        "consultation": {"provider_id": "P2", "start": "10:00", "end": "10:30"},
        "wait_minutes": 20
    }
]

Explanation: Provider P1 has 40 contiguous minutes of lab time, yielding two 30-minute appointments (09:00-09:30 and 09:10-09:40). Provider P2 has 30 continuous minutes (10:00-10:30). Both pairs have a wait time between 0 and 60 minutes.