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 ...