Scheduled Payments, Cancellation, and Top-N Payers Update

Context

You are extending an in-memory payment service that already supports:

• Accounts with balances
• Atomic debit/credit transfers between accounts
• A "top-N payers" leaderboard based on total outgoing spend from executed payments

Add scheduled payments and a cancellation API. Ensure correctness, efficiency, concurrency safety, idempotency, and clear ordering semantics.

Requirements

1. API additions
   • schedulePayment(timestamp, sourceAccountId, targetAccountId, amount, delay) -> String
     • Returns a paymentId
     • Payment becomes due at dueTime = timestamp + delay
   • runDue(timestamp) -> String
     • Executes all payments with dueTime <= timestamp
     • Execute in chronological order; if multiple have the same dueTime, use a deterministic tie-breaker (e.g., sequence number)
     • Returns a summary string of execution order as a comma-separated sequence of affected accountIds in the exact order applied: for each executed payment append "sourceAccountId,targetAccountId"
       • Example return: "S1,T1,S2,T2" for two executed payments: S1->T1 then S2->T2
   • cancel(paymentId) -> boolean
     • Prevents execution if the payment has not yet been processed
     • Returns true if the payment transitioned to canceled; false otherwise (already executed, already canceled, or not found)
2. Top-N payers
   • Scheduled payments count towards outgoing spend only when they execute (assumption; clarify if otherwise)
   • Executing a scheduled payment must update the existing top-N payers structure
3. Assumptions to state explicitly
   • Clock model: monotonic time within a shard/process; dueTime computed as timestamp + delay
   • Concurrency model: multiple threads may schedule or cancel; a single-threaded executor (or lock-guarded critical section) runs runDue per shard to enforce ordering
   • Idempotency: retrying runDue or schedule/cancel should not cause duplicate transfers
   • Insufficient funds behavior: define and document (see Solution for a default)
4. Data structures
   • Use efficient structures (e.g., maps for lookup, a min-heap keyed by dueTime)
5. Analysis
   • Provide complexity analysis (time/memory) for schedulePayment, cancel, runDue, and top-N updates
6. Deliverables
   • Clear API semantics and ordering rules
   • Data model and data structures
   • Concurrency and idempotency strategy
   • Example walk-through
   • Complexity analysis