//Job Scheduling
import java.util.*;

class Job {
    int id;
    int deadline;
    int profit;

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

public class JobScheduling {

    static class JobComparator implements Comparator<Job> {
        public int compare(Job j1, Job j2) {
            return j2.profit - j1.profit;
        }
    }

    public static int jobSequence(Job[] jobs, int n) {
        Arrays.sort(jobs, new JobComparator());
        
        int[] slot = new int[n];
        Arrays.fill(slot, 0);
        
        int[] jobSequence = new int[n];
        int count = 0;
        int totalProfit = 0;

        for (int i = 0; i < n; i++) {
            for (int j = jobs[i].deadline - 1; j >= 0; j--) {
                if (slot[j] == 0) {
                    slot[j] = 1;
                    jobSequence[j] = jobs[i].id;
                    totalProfit += jobs[i].profit;
                    count++;
                    break;
                }
            }
        }

        System.out.println("Scheduled jobs:");
        for (int i = 0; i < n; i++) {
            if (slot[i] == 1) {
                System.out.println("Job ID: " + jobSequence[i] + ", Profit: " + jobs[i].profit);
            }
        }
        System.out.println("Total profit: " + totalProfit);

        return count;
    }

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

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

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

        jobSequence(jobs, n);
        scanner.close();
    }
}

/*
Test Case 1:
Input:
5
1 2 50
2 1 10
3 2 20
4 1 30
5 3 40

Expected Output:
Scheduled jobs:
Job ID: 1, Profit: 50
Job ID: 5, Profit: 40
Total profit: 90

Test Case 2:
Input:
4
1 4 30
2 1 20
3 2 10
4 1 40

Expected Output:
Scheduled jobs:
Job ID: 4, Profit: 40
Job ID: 1, Profit: 30
Total profit: 70
*/