Implement Job Sequencing with deadlines using Greedy strategy.

#include <stdbool.h>

#include <stdio.h>

#include <stdlib.h>

// A structure to represent a Jobs

typedef struct Jobs {

   char id; // Jobs Id

   int dead; // Deadline of Jobs

   int profit; // Profit if Jobs is over before or on deadline

} Jobs;

// This function is used for sorting all Jobss according to

// profit

int compare(const void* a, const void* b){

   Jobs* temp1 = (Jobs*)a;

   Jobs* temp2 = (Jobs*)b;

   return (temp2->profit - temp1->profit);

}

// Find minimum between two numbers.

int min(int num1, int num2){

   return (num1 > num2) ? num2 : num1;

}

int main(){

   Jobs arr[] = { 

      { 'a', 2, 100 },

      { 'b', 2, 20 },

      { 'c', 1, 40 },

      { 'd', 3, 35 },

      { 'e', 1, 25 }

   };

   int n = sizeof(arr) / sizeof(arr[0]);

   printf("Following is maximum profit sequence of Jobs: \n");

   qsort(arr, n, sizeof(Jobs), compare);

   int result[n]; // To store result sequence of Jobs

   bool slot[n]; // To keep track of free time slots

   // Initialize all slots to be free

   for (int i = 0; i < n; i++)

      slot[i] = false;

   // Iterate through all given Jobs

   for (int i = 0; i < n; i++) {

      // Find a free slot for this Job

      for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) {

         // Free slot found

         if (slot[j] == false) {

            result[j] = i;

            slot[j] = true;

            break;

         }

      }

   }

   // Print the result

   for (int i = 0; i < n; i++)

      if (slot[i])

         printf("%c ", arr[result[i]].id);

   return 0;

}

Output: