Untitled

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

class Job {
    int id, deadline, profit;

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

public class Main {
    public static void jobSequencing(Job[] jobs) {
        // Step 1: Sort jobs by decreasing profit
        Arrays.sort(jobs, (a, b) -> b.profit - a.profit);

        // Step 2: Find the maximum deadline to determine the size of the schedule
        int maxDeadline = 0;
        for (Job job : jobs) {
            maxDeadline = Math.max(maxDeadline, job.deadline);
        }

        // Step 3: Create an array to store the scheduled jobs
        int[] schedule = new int[maxDeadline + 1];  // Slots for jobs (1-based index)
        Arrays.fill(schedule, -1);  // Mark all slots as free

        int totalProfit = 0;
        int jobCount = 0;

        // Step 4: Process each job and schedule it in the latest available slot before the deadline
        for (Job job : jobs) {
            for (int j = job.deadline; j > 0; j--) {
                if (schedule[j] == -1) { // If slot is available
                    schedule[j] = job.id;
                    totalProfit += job.profit;
                    jobCount++;
                    break;
                }
            }
        }

        // Step 5: Print results
        System.out.println("Scheduled Jobs:");
        for (int i = 1; i <= maxDeadline; i++) {
            if (schedule[i] != -1)
                System.out.print("J" + schedule[i] + " ");
        }
        System.out.println("\nTotal Profit: " + totalProfit);
    }

    public static void main(String[] args) {
        Job[] jobs = {
            new Job(1, 2, 100),
            new Job(2, 1, 50),
            new Job(3, 2, 10),
            new Job(4, 1, 20),
            new Job(5, 3, 30)
        };

        jobSequencing(jobs);
    }
}