Aggregate loans and match repayments

Problem Statement

In lending platforms, borrowers can take out multiple distinct loans over time and submit repayments that must be applied against their outstanding balances. Your task is to implement a loan matching engine that applies repayment transactions against existing loans.

Each loan has a loan_id, user_id, initial amount (in cents), and a timestamp. Each repayment has a payment_id, user_id, amount (in cents), and a timestamp.

Repayments should be allocated according to the following rules:

1. Repayments must be processed in chronological order by payment timestamp.
2. A repayment can only be applied to loans belonging to the same user_id that were issued on or before the payment's timestamp (loan.timestamp <= payment.timestamp).
3. Outstanding loans for a user are paid off in first-in, first-out (FIFO) order based on loan.timestamp. If two loans have the same timestamp, break ties lexicographically by loan_id.
4. If a repayment exceeds the remaining balance of the oldest loan, that loan is fully paid off, and the remaining repayment amount cascades to the next eligible loan.
5. Any portion of a repayment that cannot be applied to an eligible loan (e.g., all current loans are paid off) is left unallocated.

Return a list of allocation records in the order they occur: {"payment_id": str, "loan_id": str, "amount_applied": int}.

Function Signature

def match_repayments(loans: list[dict], repayments: list[dict]) -> list[dict]:
    pass

Input Formats

• loans: List of dicts, each with keys: "loan_id" (str), "user_id" (str), "amount" (int), "timestamp" (int).
• repayments: List of dicts, each with keys: "payment_id" (str), "user_id" (str), "amount" (int), "timestamp" (int).

Constraints

• 1 <= len(loans), len(repayments) <= 10^5
• 1 <= amount <= 10^9 (all amounts are positive integers)
• All loan_ids within loans are unique.
• All payment_ids within repayments are unique.
• Timestamps are non-negative integers.

Examples

Example 1

loans = [
    {"loan_id": "L1", "user_id": "U1", "amount": 100, "timestamp": 1},
    {"loan_id": "L2", "user_id": "U1", "amount": 150, "timestamp": 3},
]
repayments = [
    {"payment_id": "P1", "user_id": "U1", "amount": 120, "timestamp": 4},
]

# Output:
[
    {"payment_id": "P1", "loan_id": "L1", "amount_applied": 100},
    {"payment_id": "P1", "loan_id": "L2", "amount_applied": 20}
]

Explanation: At timestamp 4, both L1 and L2 exist. P1 pays off L1 completely (100 applied), leaving 20 remaining from the payment, which is applied to L2.

Example 2

loans = [
    {"loan_id": "L1", "user_id": "U1", "amount": 100, "timestamp": 5},
]
repayments = [
    {"payment_id": "P1", "user_id": "U1", "amount": 50, "timestamp": 2},
]

# Output:
[]

Explanation: P1 occurred at timestamp 2, but L1 was not created until timestamp 5. The payment cannot be matched to future loans, so no allocations occur.