Job Sequencing (NEW)

import java.util.Arrays;
import java.util.Scanner;

// Job class to hold information about each job.
class Job {
    int id;       // Job ID
    int profit;   // Profit of the job
    int deadline; // Deadline of the job
    
    // Constructor to initialize job details
    public Job(int id, int profit, int deadline) {
        this.id = id;
        this.profit = profit;
        this.deadline = deadline;
    }
}

// Comparator to sort jobs based on profit in descending order
class JobComparator implements java.util.Comparator<Job> {
    @Override
    public int compare(Job job1, Job job2) {
        return job2.profit - job1.profit; // Sorting in descending order of profit
    }
}

public class Main {

    // Function to perform Job Sequencing with Deadlines
    public static void jobSequencing(Job[] jobs, int n) {
        // Sort the jobs based on profit in descending order
        Arrays.sort(jobs, new JobComparator());
        
        // Find the maximum deadline to determine the size of the result array
        int maxDeadline = 0;
        for (int i = 0; i < n; i++) {
            if (jobs[i].deadline > maxDeadline) {
                maxDeadline = jobs[i].deadline;
            }
        }
        
        // Array to store the result (sequenced jobs)
        int[] result = new int[maxDeadline];
        
        // Initialize all slots as empty (-1 means no job is scheduled)
        Arrays.fill(result, -1);
        
        // Variable to track total profit
        int totalProfit = 0;
        
        // Iterate over all jobs
        for (int i = 0; i < n; i++) {
            // Find a free slot for the job (starting from the latest available slot)
            for (int j = jobs[i].deadline - 1; j >= 0; j--) {
                if (result[j] == -1) { // If the slot is free
                    result[j] = jobs[i].id; // Schedule the job
                    totalProfit += jobs[i].profit; // Add profit
                    break;
                }
            }
        }
        
        // Print the scheduled jobs and total profit
        System.out.println("Jobs scheduled in the sequence are:");
        for (int i = 0; i < maxDeadline; i++) {
            if (result[i] != -1) {
                System.out.print("Job " + result[i] + " ");
            }
        }
        System.out.println();
        System.out.println("Total Profit = " + totalProfit);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Take input for number of jobs
        System.out.print("Enter number of jobs: ");
        int n = scanner.nextInt();

        // Create an array of jobs
        Job[] jobs = new Job[n];

        // Take input for jobs (id, profit, deadline)
        System.out.println("Enter job details (ID Profit Deadline):");
        for (int i = 0; i < n; i++) {
            System.out.print("Job " + (i + 1) + ": ");
            int id = scanner.nextInt();
            int profit = scanner.nextInt();
            int deadline = scanner.nextInt();
            jobs[i] = new Job(id, profit, deadline);
        }

        // Call the job sequencing function
        jobSequencing(jobs, n);

        scanner.close();
    }
}




 GreedyJob(d, J, n)
{
    // J is the set of jobs that can be completed by their deadlines.
    J := {1};  // Start with the first job

    for i := 2 to n do
    {
        // Check if adding job i to the set J allows all jobs in J to be completed by their deadlines.
        if (all jobs in J ∪ {i} can be completed by their deadlines) then
        {
            J := J ∪ {i};  // Add job i to the set
        }
    }
}



 Algorithm JS(d, p, n)
// d[i] > 1, 1 ≤ i ≤ n are the deadlines, n > 1.
// The jobs are ordered such that p[1] > p[2] > ... > p[n].
// J[i] is the ith job in the optimal solution, 1 ≤ i ≤ k.
// At termination, d[J[i]] < d[J[i+1]], 1 ≤ i < k.
{
    rf[0] := J[0] := 0;  // Initialize.
    J[1] := 1;           // Include job 1 in the solution.
    k := 1;

    for i := 2 to n do
    {
        // Consider jobs in non-increasing order of profit p[i].
        // Find position for job i and check feasibility of insertion.
        r := k;

        while ((d[J[r]] > d[i]) and (d[J[r]] ≠ r)) do
        {
            r := r - 1;
        }

        if ((d[J[r]] < d[i]) and (d[i] > r)) then
        {
            // Insert job i into J[].
            for q := k to (r + 1) step -1 do
            {
                J[q + 1] := J[q];
            }
            J[r + 1] := i;
            k := k + 1;
        }
    }
    return k;
}