Suppose there are n jobs, each with a start time, end time, and a corresponding profit. The goal is to schedule these jobs in a way that the sum of their profits is maximized while ensuring that no two jobs overlap in time. Given the arrays of start_time
, end_time
, and profit
, calculate the maximum profit that can be obtained.
Note: Selecting a job that finishes at time t means you can pick the next job that starts at the same time t or later.
Constraints:
1≤ start_time.length
== end_time.length
== profit.length
≤ 103
1≤ start_time[i]
< end_time[i]
≤105
1≤ profit[i]
≤104