Match payments to invoices with fallback rules

You are given two datasets: - `invoices`: each invoice has `invoice_id`, `date`, `amount` - `payments`: each payment has `payment_id`, optional `invoice_id` (may be missing/empty), `date`, `amount` You must match each payment to **at most one** invoice (and each invoice to **at most one** payment) according to rules below, then output the matched invoice (or unmatched) for each payment. ## Part 1 — Match by invoice_id If a payment has a non-empty `invoice_id`, match it to the invoice with the same `invoice_id` if it exists and is not already matched. If no such invoice exists (or already matched), treat the payment as unmatched. ## Part 2 — Fallback to amount/date when no invoice_id If a payment has no `invoice_id`, attempt to match it by: - Find invoices with the **same amount** that are not already matched. - Choose the invoice with the **earliest date** among candidates. - If no candidate exists, payment remains unmatched. This logic must coexist with Part 1 (i.e., still prefer `invoice_id` when present). ## Part 3 — Forgiveness (tolerance) window You are given a non-negative integer `forgiveness`. If a payment has no `invoice_id`, it may match any unmatched invoice whose amount is within: - `invoice.amount ∈ [payment.amount - forgiveness, payment.amount + forgiveness]` Choose the invoice with the **earliest date** among candidates. ## Output For each payment (in input order), output the matched invoice id (or `None`/empty if unmatched). Also specify how you handle ties (same date) deterministically. ## Notes - Assume `date` is comparable (e.g., ISO `YYYY-MM-DD`). - Discuss complexity and data structures needed to support efficient earliest-date selection.