Problem statement

https://binarysearch.com/problems/Package-Matching/

Solution

I spend some time, trying to understand problem statement, it is not very well formulated. The idea of solution is the following. Let us sort sales and buyers and then keep offerc is sorted list with avaliable offers we have. Each time we have new sell we add all buyers which have some money to this moment - you can look at it as two pointers approach. We will keep amount of moneys for these people and then we use bisect_left in our sorted list to find the person with smallest amount of money who can afford to buy this package - here we use greedy strategy.

Complexity

It is O(n log n + m log m + m log n) for time, where n is the size of sales and m is the size of buyers and O(n) for space.

Code

#### Code by awice
class Solution:
    def solve(self, S, B):
        S, B = sorted(S), sorted(B)

        ans = j = 0
        offers = SortedList()
        for d, p in S:
            while j < len(B) and B[j][0] <= d:
                offers.add(B[j][1])
                j += 1

            index = offers.bisect_left(p)
            if index < len(offers):
                offers.pop(index)
                ans += 1

        return ans