Job Scheduling Problem in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
#include <stdlib.h>

typedef struct {char id;int d,p;} Job;
int cmp(const void* a,const void* b){return ((Job*)b)->p - ((Job*)a)->p;}

int main(){
    Job jobs[]={{'A',4,20},{'B',1,10},{'C',1,40},{'D',1,30}};
    int n=4; qsort(jobs,n,sizeof(Job),cmp);
    int slot[10]={0}, res[10]; 
    for(int i=0;i<n;i++)
        for(int j=jobs[i].d;j>0;j--)
            if(!slot[j]){slot[j]=1;res[j]=i;break;}
    for(int i=1;i<10;i++) if(slot[i]) printf("%c ",jobs[res[i]].id);
}

C Output

Input:  
{Job: {A,B,C,D}, Deadline: [4,1,1,1], Profit: [20,10,40,30]} 

Output:  
C A

C++ Program

#include <bits/stdc++.h>
using namespace std;
struct Job{string id;int d,p;};
int main(){
    vector<Job> a={{"J1",2,100},{"J2",1,50},{"J3",2,10},{"J4",1,20}};
    sort(a.begin(),a.end(),[](auto &x,auto &y){return x.p>y.p;});
    vector<int> slot(10,-1);
    for(int i=0;i<a.size();i++)
        for(int j=a[i].d;j>0;j--)
            if(slot[j]==-1){slot[j]=i;break;}
    for(int i=1;i<10;i++) if(slot[i]!=-1) cout<<a[slot[i]].id<<" ";
}

C++ Output

Input:  
{Job: {J1,J2,J3,J4}, Deadline: [2,1,2,1], Profit: [100,50,10,20]} 

Output:  
J1 J2

JAVA Program

import java.util.*;
class Main{
    static class Job{String id;int d,p;Job(String i,int d,int p){id=i;this.d=d;this.p=p;}}
    public static void main(String[] args){
        List<Job> jobs=Arrays.asList(new Job("X",3,35),new Job("Y",1,30),new Job("Z",2,25));
        jobs.sort((a,b)->b.p-a.p);
        String[] slot=new String[10];
        for(Job jb:jobs)
            for(int t=jb.d;t>0;t--)
                if(slot[t]==null){slot[t]=jb.id;break;}
        for(int i=1;i<10;i++) if(slot[i]!=null) System.out.print(slot[i]+" ");
    }
}

JAVA Output

Input:  
{Job: {X,Y,Z}, Deadline: [3,1,2], Profit: [35,30,25]} 

Output:  
X Y

Python Program

jobs=[('P',2,60),('Q',1,100),('R',2,20),('S',1,40)]
jobs.sort(key=lambda x:x[2],reverse=True)
slot=[None]*10
for j in jobs:
    for t in range(j[1],0,-1):
        if slot[t] is None:
            slot[t]=j[0]
            break
print([x for x in slot if x])

Python Output

Input:  
[('P',2,60), ('Q',1,100), ('R',2,20), ('S',1,40)] 

Output:  
['Q', 'P']

Deep Explanation

Problem Restatement

In the Job Scheduling Problem, you have jobs, each with a deadline and a profit. You can only work on one job at a time, and each job takes exactly one unit of time. We want to select the sequence of jobs that will give us maximum total profit without violating any deadlines. 

How It Works

The algorithm is to sort the jobs by profit in descending order and greedily assign each job to the most recent available time slot prior to its deadline. This will prioritize higher-profit jobs while later deadlines leave space for additional jobs.

Example (C Input Example)

Jobs:

A → deadline 4, profit 20

B → deadline 1, profit 10

C → deadline 1, profit 40

D → deadline 1, profit 30

Step 1: Order by profit: C(40), D(30), A(20), B(10)

Step 2: Schedule:

C → deadline 1 → put in slot 1

D → deadline 1 → slot 1 occupied, skip

A → deadline 4 → put in slot 4

B → deadline 1 → skip

Final: C, A with profit 60.

Real-Life Analogy

Suppose you own a TV station with hourly slots. You have ads from different payers, each of whom will not advertise earlier than some specified time. To obtain the most revenue, you select the most expensive ads first and schedule them as late as possible within their allowable time. Then you can place other valuable ads earlier.

Why It Matters

This question simulates resource allocation in profit-oriented scenarios — from CPU task scheduling, in which some tasks have deadlines, to event scheduling where priority is determined by ROI. It's also widely used as an interview problem because it unites greedy algorithms and array manipulation.

Learning Insights

One important thing to note is that greedy choice property applies here: selecting the most profitable job first results in an optimal solution. Second, knowing how to utilize an array to simulate time slots is a valuable skill for competitive programming.

Common Pitfalls

Inexperienced users tend to sort by deadline rather than profit, which can result in less-than-optimal outcomes. Another error is booking jobs at the first available slot rather than the last prior to the deadline — that squanders time slots that could be occupied by jobs with earlier deadlines.

Time and Space Complexity

Sorting is O(n log n). Scheduling each job in its slot loop is O(n × m) where m is the maximum deadline, but with union-find optimizations it can be done in less time. Space is O(m) for slots.

Real-World Applications

Manufacturing, where jobs have deadlines with varying payouts and machines have fixed capacity.

Advertisement scheduling for broadcast media.

Cloud computing job assignment to maximize billing revenue.

Delivery scheduling in logistics with per-order profits.

SEO-Friendly Closing Paragraph

The Job Scheduling Problem, or Job Sequencing with Deadlines, is an old greedy algorithm problem applied in scheduling systems, manufacturing, and revenue maximization. Sorting jobs according to profit and scheduling every one in the most recent available slot before the deadline will get you the highest possible profit without violating time constraints. This strategy operates smoothly in O(n log n) time and has broad usage in CPU scheduling, commercials slots, and transportation, making it a necessary algorithm for coding interviews and practical optimization scenarios.