BinarySearch 0578 Paying Workers With Coins

Problem statement

https://binarysearch.com/problems/Paying-Workers-With-Coins/

Solution

Start with the biggest salary, imagine that we have x options for it. Then for the second biggest salary if we have y coins which good values, than we have y - 1 options and so on. In the end we multiply all these numbers.

Complexity

It is O(n log n + m log m + m log n) for time, where n = len(C) and m = len(S). Space is O(m + n).

Code

class Solution:
    def solve(self, C, S):
        S, C, ans = sorted(S), sorted(C), 1
        for i, sal in enumerate(S[::-1]):
            idx = len(C) - bisect.bisect_left(C, sal)
            ans = (ans * (idx - i)) % (10**9 + 7)
        return ans