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 \leq$ start_time.length $==$ end_time.length $==$ profit.length $\leq$ $10^3$

• $1 \leq$ start_time[i] $<$ end_time[i] $\leq 10^5$

• $1 \leq$ profit[i] $\leq 10^4$

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

In the naive approach, we systematically explore all possible combinations of scheduling jobs to find the one that provides us the maximum profit. For each of the $n$ jobs, there are two choices:

• Schedule the job.

• Do not schedule the job.

This results in $2^n$ potential combinations. We evaluate each combination, calculating the total profit achieved while ensuring that no two jobs overlap in their time frames, as that would violate the constraint. After checking all combinations, we select the one that maximizes profit and adheres to the non-overlapping constraint, representing the optimal job schedule.

Since this approach requires an exhaustive search process for $2^n$ potential combinations, it leads to a time complexity of $O(2^n)$. Then, to calculate the total profit, the algorithm checks for overlaps by comparing each pair of jobs in the combination. This overlap-checking process takes $O(n^2)$ time for each combination. As a result, the overall time complexity of this approach becomes $O(2^n \times n^2)$. However, the space complexity of this solution is $O(n)$ because the maximum length of a combination during the process can be $n$.

When we read the problem statement, there are a couple of points we need to consider:

• The problem requires us to find the schedule that provides maximum profit, which, in other words, is the optimal solution.

• A job cannot be scheduled if an overlapping job has already been scheduled. This implies that the task of scheduling any job under consideration is dependent on the previously scheduled jobs, which represents an optimal substructure property.

The above points signify that this problem can be solved using Dynamic Programming since it exhibits characteristics typical of such problems. We can find the optimal solution for scheduling jobs to maximize the associated profit by breaking the problem into subproblems. In each subproblem, we'll consider scheduling one job at a time, taking into account the already scheduled jobs and their conflicts. This allows us to gradually build up the optimal schedule based on the optimal solutions to smaller subproblems.

Another important aspect of solving this problem is knowing when two jobs would overlap. Let's say there are two jobs, $A$ and $B$, then both will overlap if: