Job Sequencing with Deadlines

Given a set of N jobs where each job i has a deadline and profit associated with it. Each job takes 1 unit of time to complete and only one job can be scheduled at a time. We earn the profit if and only if the job is completed by its deadline.

Find the maximum profit and the number of jobs done.

Examples

Input: id = [1,2,3,4,5], deadline = [2,1,2,1,3], profit = [100,19,27,25,15]

Output: [3, 142]

Do job 3 (profit 27), job 1 (profit 100) and job 5 (profit 15) for max profit 142.

Constraints

• 1 <= N <= 10^5
• 1 <= deadline[i] <= N
• 1 <= profit[i] <= 500

Complexity Analysis

Time

O(N log N + N * maxDeadline)

or O(N log N) using a Disjoint Set.

Space

O(maxDeadline)

slot array.

Test Cases

#1 Standard case

Input: id = [1,2,3,4,5], deadline = [2,1,2,1,3], profit = [100,19,27,25,15]

Expected: [3,142]

#2 Limited deadlines

Input: id = [1,2,3,4], deadline = [4,1,1,1], profit = [20,10,40,30]

Expected: [2,60]