You are given an array of jobs where every individual job contains a unique identifier, a strict deadline, and a specific profit associated with completing it. Every job takes exactly one unit of time to complete, meaning the absolute minimum possible deadline for any job is 1. Your objective is to maximize your total accumulated profit if only one single job can be scheduled at any given time. Return the total number of jobs you successfully managed to complete and the maximum total profit you earned.
Note that a job can be completed at any time slot as long as the assigned slot falls before or exactly on its specific deadline.
Example 1
Input: jobs = [[1, 4, 20], [2, 1, 10], [3, 1, 40], [4, 1, 30]]
Output: [2, 60]
Explanation: Job 3 can be scheduled before deadline 1 for profit 40. Job 1 can be scheduled before deadline 4 for profit 20. The maximum profit is 40 + 20 = 60, and 2 jobs are completed.
Example 2
Input: jobs = [[1, 2, 100], [2, 1, 19], [3, 2, 27], [4, 1, 25], [5, 3, 15]]
Output: [3, 142]
Explanation: One optimal schedule completes job 3 in slot 1, job 1 in slot 2, and job 5 in slot 3. The total profit is 27 + 100 + 15 = 142.
Approach
A job with larger profit is more valuable because every scheduled job consumes exactly one time slot. Therefore, profitable jobs should be considered before less profitable jobs.
After a job is chosen, placing it in the latest free slot before its deadline is safe. This keeps earlier slots open for jobs that may have smaller deadlines. If no valid slot exists for that job, scheduling it would block a better already chosen set, so it is skipped.
This greedy choice works because each accepted job is placed without reducing the chance of scheduling other high-profit jobs as much as possible.
Algorithm
Sort all jobs in descending order of profit so the most valuable jobs are considered first.
Find the maximum deadline to know how many scheduling slots may be needed.
Create a timeline of free slots from
1to the maximum deadline.For each job in sorted order, search backward from its deadline to find the latest free slot.
If a free slot is found, place the job there, increase the completed-job count, and add its profit.
After all jobs are checked, return the completed-job count and total profit.
Dry Run
Job
Solution
#include <bits/stdc++.h>using namespace std;struct Job { int id; int deadline; int profit;};class Solution {public: // Orders jobs by higher profit first. static bool comparison(Job first, Job second) { return first.profit > second.profit; } // Returns the number of jobs done and the maximum profit. vector<int> jobScheduling(Job jobs[], int n) { // Consider higher-profit jobs before lower-profit jobs. sort(jobs, jobs + n, comparison); int maxDeadline = 0; // Find the largest deadline to size the timeline. for (int i = 0; i < n; i++) { // A larger deadline increases the required timeline length. if (jobs[i].deadline > maxDeadline) { maxDeadline = jobs[i].deadline; } } vector<int> timeline(maxDeadline + 1, -1); int countJobs = 0; int totalProfit = 0; // Try to schedule each job in descending profit order. for (int i = 0; i < n; i++) { // Search for the latest free slot before this job's deadline. for (int slot = jobs[i].deadline; slot > 0; slot--) { // A free slot allows this job to be scheduled. if (timeline[slot] == -1) { timeline[slot] = jobs[i].id; countJobs++; totalProfit += jobs[i].profit; break; } } } return {countJobs, totalProfit}; }};// Driver codeint main() { Job jobs[] = {{1, 2, 100}, {2, 1, 19}, {3, 2, 27}, {4, 1, 25}, {5, 3, 15}}; int n = sizeof(jobs) / sizeof(jobs[0]); // instance for class Solution Solution sol; vector<int> result = sol.jobScheduling(jobs, n); cout << result[0] << ' ' << result[1] << '\n'; return 0;}Time Complexity
Time Complexity: O(N log N + N * M). Sorting the entire job array natively takes O(N log N) time. The outer loop traverses the N jobs, and the inner loop travels backward up to the maximum deadline M, resulting in an additional worst-case time complexity of O(N * M).
Space Complexity: O(M). We strictly allocate auxiliary memory for the timeline tracking array which scales linearly with the absolute highest deadline integer M.
Interview follow-up Questions
If a job has a deadline of day 4, assigning it to day 1 safely fulfills its requirement but selfishly blocks a different job that might strictly expire on day 1. By searching backward from the absolute limit of day 4, we delay the job as much as possible. This preserves the early timeline slots strictly for high-profit jobs that expire extremely quickly.
Be the first to add a comment.