import java.util.*;

class Job {
    int id, deadline, profit;

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

public class JobScheduling {

    public static int scheduleJobs(Job[] jobs, int n) {
        Arrays.sort(jobs, (a, b) -> b.profit - a.profit);

        boolean[] slots = new boolean[n];
        int maxProfit = 0;

        for (Job job : jobs) {
            for (int j = Math.min(n, job.deadline) - 1; j >= 0; j--) {
                if (!slots[j]) {
                    slots[j] = true;
                    maxProfit += job.profit;
                    System.out.print("Job " + job.id + " ");
                    break;
                }
            }
        }

        System.out.println("\nMax Profit: " + maxProfit);
        return maxProfit;
    }

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

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

        for (int i = 0; i < n; i++) {
            System.out.print("Enter job ID, deadline, and profit: ");
            jobs[i] = new Job(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }

        scheduleJobs(jobs, n);
        sc.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;
}