#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int id;      
    int deadline;
    int profit;  
} Job;

int compare(const void* a, const void* b) {
    Job* job1 = (Job*)a;
    Job* job2 = (Job*)b;
    return job2->profit - job1->profit; 

int jobSequence(Job* jobs, int n) {
    qsort(jobs, n, sizeof(Job), compare);
    
    int* jobSequence = (int*)malloc(n * sizeof(int)); 
    int* slot = (int*)malloc(n * sizeof(int)); 
    for (int i = 0; i < n; i++) {
        slot[i] = 0;
    }
    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;   
            }
        }
    }
    printf("Scheduled jobs:\n");
    for (int i = 0; i < n; i++) {
        if (slot[i] == 1) {
            printf("Job ID: %d, Profit: %d\n", jobSequence[i], jobs[i].profit);
        }
    }
    printf("Total profit: %d\n", totalProfit);

    free(jobSequence);
    free(slot);
    return count; 
}

int main() {
    int n;
    printf("Enter the number of jobs: ");
    scanf("%d", &n);
    Job* jobs = (Job*)malloc(n * sizeof(Job));
    printf("Enter job ID, deadline, profit for each job:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &jobs[i].id, &jobs[i].deadline, &jobs[i].profit);
    }
    jobSequence(jobs, n);
    free(jobs);
    return 0;
}