There are n jobs on offer. Job i runs from time startTime[i] to time endTime[i] and pays profit[i]. You can work on only one job at a time, so the jobs you take must not overlap. Return the largest total pay you can earn.
A job that ends at time t does not clash with one that starts at time t: you can finish one and begin the next at the same moment.
Take the job from 2 to 6 (pays 60), then the one from 6 to 9 (pays 20): 80. The chain 1 → 4 then 4 → 7 touches end to start as well, but pays only 70.
The two short jobs fit together for 9, but the single long job pays 10.
Each job ends exactly when the next begins, so all three fit.
Constraints
n == startTime.length == endTime.length == profit.length1 <= n <= 5 × 10⁴1 <= startTime[i] < endTime[i] <= 10⁹1 <= profit[i] <= 10⁴Sort the jobs by end time. The best pay from the first k jobs either skips job k, or takes it plus the best pay from the jobs that end no later than job k starts.
80