Skip to main content
Back to ChallengesJob Sequencing with DeadlinesHard 45 min

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]
Output
Click "Run Code" to see output here...