Untitled

 avatar
unknown
plain_text
5 months ago
1.8 kB
6
Indexable
#!/bin/python3

import sys
import bisect
import heapq

def countMaximumDays(lend, payback):
    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 min-heaps of payback amounts
    lend_to_paybacks = {}
    for l, p in lenders:
        if l not in lend_to_paybacks:
            lend_to_paybacks[l] = []
        # Push payback amounts into a min-heap for each lend amount
        heapq.heappush(lend_to_paybacks[l], p)

    # 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.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 = heapq.heappop(lend_to_paybacks[lend_amount])
        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

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    lend = []
    for _ in range(n):
        lend_item = int(sys.stdin.readline())
        lend.append(lend_item)
    n2 = int(sys.stdin.readline())
    payback = []
    for _ in range(n2):
        payback_item = int(sys.stdin.readline())
        payback.append(payback_item)
    result = countMaximumDays(lend, payback)
    print(result)
Editor is loading...
Leave a Comment