You are given a set of jobs, each with a deadline and a profit. Each job takes one unit of time. A job can only be completed before or on its deadline. Return the maximum profit achievable by scheduling at most one job at each time slot. Pattern focus: Exchange Argument. Sort jobs by profit and place each job in the latest available slot to preserve earlier slots for future high-value jobs.
jobs = list of [deadline, profit] pairs
maximum profit achievable
Example 1:
Input:
jobs = [[2,100],[1,19],[2,27],[1,25],[3,15]]
Output:
142
Explanation:
A profitable schedule is jobs with profits 100, 27, and 15.
Example 2:
Input:
jobs = [[1,10],[1,20],[2,30]]
Output:
50
Explanation:
Choose the 20-profit job at slot 1 and the 30-profit job at slot 2.
Example 3:
Input:
jobs = [[1,100],[2,50],[2,10]]
Output:
150
Explanation:
Schedule the 100-profit job first and the 50-profit job second.