Leetcode: Maximum profit in job scheduling (#1235) solution and explanation

PROBLEM:

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].
You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.
If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:
Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

SOLUTION:

The idea is the following:

1. add all the times-points (of both jobs begins and ends) to one sorted structure (it can be sorted array or as below priority queue).
2. iterate through every time-point. For every point N have local max (max profit sum of non overlaping jobs which have finished before N inclusive).

Here’s an example:
let’s asume
startTime = [1,2,3,3,4,5], endTime = [3,4,5,6,6,8], profit = [50,10,40,70,10,100]
then, our jobs will look like on this:

Let’s also create special map for local MAX-es and one variable for global max.
Now, we’ll iterate through our points. Start with 1:

we see, that one of our jobs starts (priority = 50) from point 1 and ends at coordinate 3, so put to pointToMax {3 -> 0 + 50} (0 is current max, 50 is profit of job starting with current point).

go to next point 2:

again, we see that job (10) starts from point 2 and ends with point 4. Add to pointToMax {4 -> 0 + 10}. 0 is current max, 10 — profit of job.
go next:

here’s interesting thigs begin:

1. update max: we are currently at point 3 and in pointToMax has entry 3 -> 50 . This means that by this moment 50 is our max. Global max becomes Math.max(50, 0) = 50 . Also, optionally, remove 3 -> 50 from map.
2. we see, that two jobs begins with 3 : (40) and (70). Let’s put entries to pointToMax about them:
   5 -> 50 + 40 = 90 (50 is our current max)
   6 -> 50 + 70 = 120

go next:

we see one job with priority 10 ends with point 4 and another job (10) begins with point 4.

1. job ends with point 4 : define if we should update global max. Take from pointToMax entry 4 -> 10 and set max = Math.max(50, 10) = 50 (where 50 is old value for max). In our case, it remains 5. Also remove this entry from pointToMax
2. new job (10) starts with 4: put into pointToMax entry 6 -> 50 + 10 (50 — global max, 10 — priority, 6 — point where is ends). However (!!!!) pointToMax already contains key 6 with higher value: 6 -> 120.
   In this case, we shouln’t update map value.

go next:

at point 5 one job (40) finishes => retrieve from pointToMax entry 5 -> 90 and update global max. max becomes 90.
also, new job (100) starts at point 5, so again add to pointToMax entry 8 -> 90 + 100 (8 — point where is ends, 90 — current max, 100 — priority).

go next, to 6.
we have some jobs ending at point 6, so retrieve from pointToMax entry 6 -> 120 and update global max. Now, it becomes 120.
no new job starts at point 6, so we don’t need to put any new entry:

we skip 7 as nothing start/ends with it, so in our solution we won’t even iterate through it. Just go next to 8.
job (100) ends with 8, so update global max: max = Math.max(120, 190) = 190.

to sum up, we see, that our response includes jobs (50), (40) and (100).