Approach #1: Sorting Events [Accepted]

Intuition

We can consider the workers in any order, so let's process them in order of skill.

If we processed all jobs with lower skill first, then the profit is just the most profitable job we have seen so far.

Algorithm

We can use a "two pointer" approach to process jobs in order. We will keep track of best, the maximum profit seen.

For each worker with a certain skill, after processing all jobs with lower or equal difficulty, we add best to our answer.

Complexity Analysis

  • Time Complexity: , where is the number of jobs, and is the number of people.

  • Space Complexity: , the additional space used by jobs.


Analysis written by: @awice.