There's a pile of concert tickets, each with a price (prices may repeat). Customers arrive one by one, and each names the most they're willing to pay. Every customer is sold the most expensive remaining ticket whose price does not exceed their maximum; that ticket is then gone. If no remaining ticket is affordable, the customer leaves empty-handed.
Write concert_tickets(prices, maxes) -> list[int]: for each customer in order, the price they paid, or -1 if they got nothing.
concert_tickets([5, 3, 7, 8, 5], [4, 8, 3]) # [3, 8, -1]
# customer 1 (max 4) takes the 3; customer 2 (max 8) takes the 8;
# customer 3 (max 3) finds nothing left at or below 3
Constraints: up to ~10^5 tickets and customers; prices and maxes up to 10**9. Scanning all tickets per customer is O(n·m) and too slow; aim for O((n + m) log n).
Show hint
each customer asks for the largest remaining price <= x. With the prices sorted that's a search, and the only extra work is making sold tickets disappear quickly.