Credit Suisse Question
1636

A team of traders have a series of trades, numbered 0-i, that they can fulfill for a client.

We have three arrays: trader, risk, and bonus.
trader[i] gives the skill level of the i th trader.
risk[i] gives the difficulty of the i th trade. Only traders with a skill level at or above risk[i] can complete trade[i]. Completion of a trade[i] gives the team a bonus of bonus[i].
What is the biggest bonus the traders can make?

Constraints
trader.length, risk.length, bonus.length >= 1 and <= 10,000.
The arrays are not necessarily in ascending order (although bonus[i] and risk[i] will always correspond to the bonus and risk of trade i).
Each trader is only able to take on at most one trade, but multiple traders can complete the same trade.
Output Format
The value returned should be the maximum profit that can be made from your trading strategy.

Example 1
Input: trader = [6, 7, 2, 8, 1], risk = [5, 4, 3, 1, 8], bonus = [9, 9, 1, 9, 4]

Output: 45

Example 2
Input: trader = [2, 10, 9, 10, 10], risk = [9, 1, 1, 6, 1], bonus = [9, 9, 8, 10, 10]

Output: 50

My Code:

def solution(risk, bonus, trader):
    max_profit = 0  # initialize the total maximum profit
    for td in trader:
        profit = 0  # initialize the potential profit a single trader can make
        for r, b in zip(risk, bonus):
            if td >= r:  # the trader can complete the trade
                if b > profit:
                    profit = b  # update the potential profit with a higher value
        max_profit += profit  # update the total maximum profit
    return max_profit

Is it possible in O(n) complexity?

Comments (2)