Untitled

 avatar
unknown
plain_text
5 months ago
1.3 kB
2
Indexable
def countMaximumDays(lend, payback):
    from bisect import bisect_left

    n = len(lend)
    # Pair lend and payback amounts
    lenders = list(zip(lend, payback))
    # Sort lenders by lend amount, then by payback amount
    lenders.sort(key=lambda x: (x[0], x[1]))
    
    # Map lend amounts to lists of payback amounts
    lend_to_paybacks = {}
    for l, p in lenders:
        if l not in lend_to_paybacks:
            lend_to_paybacks[l] = []
        lend_to_paybacks[l].append(p)

    # For each lend amount, the payback amounts are sorted due to initial sorting
    # Create a sorted list of lend amounts
    lend_amounts = sorted(lend_to_paybacks.keys())

    day = 0
    prev_payback = 0

    while True:
        # Find the index of the smallest lend amount >= prev_payback
        idx = bisect_left(lend_amounts, prev_payback)
        if idx == len(lend_amounts):
            break  # No lender can cover the payback
        lend_amount = lend_amounts[idx]
        # Get the lender with the minimal payback amount
        payback_i = lend_to_paybacks[lend_amount].pop(0)
        if not lend_to_paybacks[lend_amount]:
            # Remove lend amount if no lenders are left
            lend_amounts.pop(idx)
            del lend_to_paybacks[lend_amount]
        prev_payback = payback_i
        day += 1

    return day
Editor is loading...
Leave a Comment