B-  3.implement Greedy Algorithm for job sequencing with deadlines.  

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

// Structure to represent a job
typedef struct {
    char id[10];   // Job ID (e.g., "J1", "J2")
    int deadline;  // Deadline (1 unit of time per job)
    int profit;    // Profit earned if completed before or on deadline
} Job;

// Comparator function to sort jobs in descending order of profit
int compareJobs(const void* a, const void* b) {
    Job* jobA = (Job*)a;
    Job* jobB = (Job*)b;
    return (jobB->profit - jobA->profit); // Higher profit comes first
}

// Function to find the minimum of two integers
int min(int a, int b) {
    return (a < b) ? a : b;
}

// Function to implement Job Sequencing with Deadlines
void jobSequencing(Job jobs[], int n) {
    // Step 1: Sort all jobs in descending order of profit
    qsort(jobs, n, sizeof(Job), compareJobs);

    // Find the maximum deadline to size our time slots array
    int maxDeadline = 0;
    for (int i = 0; i < n; i++) {
        if (jobs[i].deadline > maxDeadline) {
            maxDeadline = jobs[i].deadline;
        }
    }

    // Result array to store scheduled job indices in time slots
    int result[maxDeadline + 1];
    // Slot array to keep track of occupied time slots
    bool slot[maxDeadline + 1];

    // Initialize all slots as free (false) and result with -1
    for (int i = 0; i <= maxDeadline; i++) {
        slot[i] = false;
        result[i] = -1;
    }

    int totalProfit = 0;
    int countJobs = 0;

    // Step 2: Iterate through all sorted jobs
    for (int i = 0; i < n; i++) {
        // Find a free slot for this job (start from the latest possible slot <= deadline)
        for (int j = min(maxDeadline, jobs[i].deadline); j > 0; j--) {
            // Free slot found
            if (!slot[j]) {
                slot[j] = true;        // Mark slot as occupied
                result[j] = i;         // Store job index
                totalProfit += jobs[i].profit;
                countJobs++;
                break;
            }
        }
    }

    // Step 3: Print the results
    printf("\n--- Job Scheduling Results ---\n");
    printf("Scheduled Sequence of Jobs: ");
    for (int i = 1; i <= maxDeadline; i++) {
        if (slot[i]) {
            printf("%s ", jobs[result[i]].id);
        }
    }
    printf("\nTotal Jobs Scheduled: %d\n", countJobs);
    printf("Total Maximum Profit: %d\n", totalProfit);
}

int main() {
    int n;

    printf("Enter the number of jobs: ");
    if (scanf("%d", &n) != 1 || n <= 0) {
        printf("Invalid input.\n");
        return 1;
    }

    Job jobs[n];

    printf("\nEnter details for each job (ID Deadline Profit):\n");
    for (int i = 0; i < n; i++) {
        printf("Job %d: ", i + 1);
        scanf("%s %d %d", jobs[i].id, &jobs[i].deadline, &jobs[i].profit);
    }

    jobSequencing(jobs, n);

    return 0;
}


OUTPUT
Enter the number of jobs: 5

Enter details for each job (ID Deadline Profit):
Job 1: J1 2 100
Job 2: J2 1 19
Job 3: J3 2 27
Job 4: J4 1 25
Job 5: J5 3 15