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.