Maximum Profit in Job Scheduling

Advanced

Maximum Profit in Job Scheduling

Imagine you are the planner for a superhero team, and you need to schedule their jobs so they can maximize their earnings. Each job has a start time, an end time, and a profit. The superheroes can only complete non-overlapping jobs, and your task is to select the jobs such that their total profit is the highest possible.

Write a function job_scheduler that takes in a list of jobs, where each job is represented as a tuple of three elements: (start_time, end_time, profit). The function should return the maximum profit the superheroes can earn by scheduling non-overlapping jobs.

Here's how the function should work:

jobs = [(1, 3, 50), (3, 5, 20), (4, 6, 30), (6, 8, 60)] print(job_scheduler(jobs)) # Output: 140 jobs = [(1, 2, 20), (2, 3, 15), (3, 4, 10)] print(job_scheduler(jobs)) # Output: 45

In the first example, the optimal jobs to take are (1,3,50), (4,6,30) and (6,8,60), giving a total profit of 140. A job can start at the moment another one ends. In the second example, all jobs can be taken because they do not overlap, resulting in a total profit of 45.

Geek
Inputs

Arg 1:

[[1,3,50],[3,5,20],[4,6,30],[6,8,60]]
Expected Output
140
Actual Output