Untitled
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