JobSequencing

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

class Job {
    int id;     // Job ID
    int profit; // Profit if job is completed
    int deadline; // Deadline by which job should be completed

    Job(int id, int profit, int deadline) {
        this.id = id;
        this.profit = profit;
        this.deadline = deadline;
    }
}

public class JobSequencing {

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

        // Input the number of jobs
        System.out.print("Enter the number of jobs: ");
        int n = scanner.nextInt();
        Job[] jobs = new Job[n];

        // Input each job's ID, profit, and deadline
        for (int i = 0; i < n; i++) {
            System.out.print("Enter job ID, profit, and deadline for job " + (i + 1) + ": ");
            int id = scanner.nextInt();
            int profit = scanner.nextInt();
            int deadline = scanner.nextInt();
            jobs[i] = new Job(id, profit, deadline);
        }

        // Calculate the maximum profit and print the job sequence
        int totalProfit = jobSequencing(jobs, n);

        System.out.println("Total Profit: " + totalProfit);
        
        scanner.close();
    }

    public static int jobSequencing(Job[] jobs, int n) {
        // Sort jobs by profit in descending order
        Arrays.sort(jobs, Comparator.comparingInt((Job job) -> job.profit).reversed());

        // Find the maximum deadline to create the job schedule array
        int maxDeadline = 0;
        for (Job job : jobs) {
            maxDeadline = Math.max(maxDeadline, job.deadline);
        }

        // Array to keep track of the free time slots
        int[] result = new int[maxDeadline + 1]; // 1-based index
        Arrays.fill(result, -1); // Initialize all time slots to -1 (indicating free)

        int totalProfit = 0;

        System.out.println("\nSelected Jobs:");
        System.out.println("Job ID | Profit | Deadline");

        // Iterate over each job
        for (Job job : jobs) {
            // Find a free time slot for this job (latest possible slot before deadline)
            for (int j = job.deadline; j > 0; j--) {
                if (result[j] == -1) { // If slot j is free
                    result[j] = job.id; // Assign job to this slot
                    totalProfit += job.profit;
                    System.out.println("   " + job.id + "    |   " + job.profit + "  |    " + job.deadline);
                    break;
                }
            }
        }

        return totalProfit;
    }
}