Approach #1: Sorting Events [Accepted]
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.
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.
Time Complexity: , where is the number of jobs, and is the number of people.
Space Complexity: , the additional space used by
Analysis written by: @awice.