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.