Untitled
unknown
plain_text
a year ago
1.3 kB
5
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