Sunday, February 21, 2010

Job Sequencing

import java.util.*;

class job
{
int p,d,jid;
job()
{
Scanner src=new Scanner(System.in);
System.out.println("enter profit");
p=src.nextInt();
System.out.println("enter deadline");
d=src.nextInt();
}
}
class slot
{
public static void main(String args[])
{
Scanner src=new Scanner(System.in);
System.out.println("enter the no.of jobs");
int n=src.nextInt();
job obj[]=new job[n];
for(int i=0;i<=n-1;i++)
{
    System.out.println("job"+(i+1));
    System.out.println("__________________");
obj[i]=new job();
obj[i].jid=i+1;
}
obj=sorting(obj);
seq(obj);
}
static job[] sorting(job temp[])
{
for(int i=0;i<=temp.length-2;i++)
for(int j=i+1;j<=temp.length-1;j++)
{
if(temp[i].p<temp[j].p)
{
job temp2=temp[i];
temp[i]=temp[j];
temp[j]=temp2;
}
}
return temp;
}
static void seq(job temp[])
{
int maxd=0,profit=0;
for(int i=0;i<=temp.length-1;i++)
{
if(temp[i].d>=maxd)
{
maxd=temp[i].d;
}
}
System.out.println("max deadline:"+maxd);
int slot[][]=new int[2][maxd];

for(int i=0;i<=maxd-1;i++)
slot[0][i]=0;

for(int i=0;i<=temp.length-1;i++)
{
    int fill=0,at=0;
for(int j=0;j<=maxd-1;j++)
{
if(slot[0][j]==0&&j<=temp[i].d-1)
{fill=1;
at=j;
}
}

if(fill==1)
{
slot[0][at]=1;
System.out.println("job "+temp[i].jid+"filled at "+at);
slot[1][at]=temp[i].jid;
profit=profit+temp[i].p;
}
}
System.out.println("max profit:"+profit);
}
}   

1 comment: