/* 7(a). W.A.P. to implement Job Scheduling with Deadlines problem using Greedy algorithm. */

#include<stdio.h>
#include<conio.h>
struct Job
{
    int d,p,v; /* Deadline, Profit, Visited status. */
};
typedef struct Job jobs;
jobs jobseq[10];
int x[10],n,maxprofit=0;
void JobSeq(void)
{
    int j,k,count=0,min,u;
    while (count < n)
    {
        min = 99;
        u = -1;
        for (j = 0; j < n; j++)
            if (jobseq[j].v == 1) /* Already visited */
                continue;
/* Select minimum deadline */
            else if ((jobseq[j].d >= 1) && (jobseq[j].d < min))
            {
                min = jobseq[j].d;
                u = j;
            }
            if (u != -1)
            {
                jobseq[u].v = 1; /* Visited */        
                maxprofit += jobseq[u].p; /* Add profit to maxprofit */
                x[count] = u+1; /* Add the job to solution vector */
                for (k = 0; k < n; k++)
                        if (jobseq[k].v == 0) /* Unvisited */
                            jobseq[k].d = jobseq[k].d - 1; /* Reduce deadline by 1 */
            }
            count++;
    }
}
void main(void)
{
    int i,j;
    clrscr();
    printf("Enter the number of jobs : ");
    scanf("%d",&n);
    printf("\nEnter profits in Descending Order :\n");
    for (i = 0; i < n; i++)
            scanf("%d",&jobseq[i].p);
            printf("\nEnter deadlines :\n");
    for (i = 0; i < n; i++)
    {
            scanf("%d",&jobseq[i].d);
            x[j] = 0; /* Initialize solution vector */
            jobseq[i].v = 0; /* All jobs are not visited */
    }
    JobSeq();
    printf("\nSelected jobs (profits shown) :\n");
    for (i = 0; i < n; i++)
    if (x[i] != 0) /* Print the profits of selected jobs only */
        printf("%d\t",jobseq[x[i]-1].p);
        printf("\n\nOptimal solution = %d",maxprofit);
        printf("\n\nSolution vector is as follows :\n");
    for (i = 0; i < n; i++) /* Print the solution vector */
        if (x[i] != 0)
            printf("%d\t",x[i]);
            getch();
}
/* OUTPUT
Enter the number of jobs : 4
Enter the profits in Descending order :
100 27 15 10
Enter the deadlines:
2 1 2 1

Selected jobs (profits shown) :
27 100

Optimal solution = 127

Solution vector is as follows :
2 1
*/