Job Sequencing Problem In C#

This article will discuss the Job sequencing problem in C#. We will achieve it using a greedy approach algorithm.

Problem statement

The job sequencing problem is a common problem that involves assigning a set of jobs to a set of machines, where each job has a deadline and a profit, and we have to get the maximum profit before the job deadline.

Given an array of jobs where each job has its deadline and profit. And Profit can be obtained only if the job is finished before the deadline. Also, every job takes a single unit of time, so the minimum possible deadline for any job is 1. So we have to get the maximum profit before the job deadline.

For example,

JobID	Deadline	Profit
1	3	90
2	1	20
3	2	30
4	1	25
5	2	15

Output

JobID:-> 4,3,1

C# code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace JobsSequencingProblemInCSharp {
    public class Jobs {
        public int JobsID {
            get;
            set;
        }
        public int Deadline {
            get;
            set;
        }
        public int Profit {
            get;
            set;
        }
    }
    public class JobsSequencingProblem {
        public static void JobsSequencing() {
            List < Jobs > Jobs = new List < Jobs > () {
                new Jobs {
                    JobsID = 1, Deadline = 3, Profit = 90
                },
                new Jobs {
                    JobsID = 2, Deadline = 1, Profit = 20
                },
                new Jobs {
                    JobsID = 3, Deadline = 2, Profit = 30
                },
                new Jobs {
                    JobsID = 4, Deadline = 1, Profit = 25
                },
                new Jobs {
                    JobsID = 5, Deadline = 2, Profit = 15
                }
            };
            // Sort Jobs in the decreasing order of profit
            Jobs = Jobs.OrderByDescending(j => j.Profit).ToList();
            // Determine the maximum deadline of job
            int maxDeadline = Jobs.Max(j => j.Deadline);
            // Initialize the slots array
            int[] slots = new int[maxDeadline];
            foreach(Jobs Job in Jobs) {
                int slot = -1;
                for (int i = Job.Deadline - 1; i >= 0; i--) {
                    if (slots[i] == 0) {
                        slot = i;
                        break;
                    }
                }
                // If the slot is available, assign the Jobs to that slot
                if (slot != -1) {
                    slots[slot] = Job.JobsID;
                }
            }
            Console.WriteLine("Selected Jobs:");
            for (int i = 0; i < maxDeadline; i++) {
                if (slots[i] != 0) {
                    Console.WriteLine("Jobs " + slots[i]);
                }
            }
        }
    }
}
Public static void Main(string[] args) {
    JobsSequencingProblem.JobsSequencing();
    Console.ReadLine();
}

Problem Explanation

This implementation is done by the greedy approach; we start by sorting the jobs in the decreasing order of the profit, and then we determine the maximum deadline of the job, then we initialize an array of slots with a length equal to the maximum deadline.

And then, we iterate through each job and find the latest available slot for that job by starting from its deadline and going backward until we find an empty slot. If we find an available slot, we assign the job to that slot. If we don't find an available slot, we skip the job.

Finally, we print the selected jobs by iterating through the slots array and printing the job ID for each non-zero slot.