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

//sort d but does not modify d; it writes the sorted indices in output
void sort(int *d, int *output, int n)
{
	int i,j;
	
	for(i=0; i<n;i++)
		output[i]=i;
	
	//selection sort	
	for(i=0; i<n; i++)
		for(j=i;j<n;j++)
			if(d[output[i]]>d[output[j]])
			{
				output[i]=output[i]^output[j];
				output[j]=output[i]^output[j];
				output[i]=output[i]^output[j];
			}
}

void schedule_guess(int* l, int* d, int n)
{
	int i, late=0, *schedule,time,flag=1;
	schedule = (int*)malloc(n*sizeof(int));
	
	sort(d, schedule, n);
	
	for(;flag;late++)
	{
		time=0;
		flag=0;
		
		for(i=0;i<n;i++)
			if(time+l[schedule[i]]<=d[schedule[i]]+late)
				time+=l[schedule[i]];
			else
			{
				flag=1;
				break;
			}
	}
	late--;
	
	printf("Optimal schedule by late guessing algorithm is: ");
	for(i=0;i<n;i++)
		printf("%d, ",schedule[i]+1);
	printf("\nMaximum lateness is %d\n",late);
}

void schedule_greedy(int* l, int* d, int n)
{
	int i, late, *schedule,time;
	schedule = (int*)malloc(n*sizeof(int));
	
	sort(d, schedule, n);
	
	for(i=0,late=0,time=0;i<n;i++)
	{
		if(time+l[schedule[i]]>d[schedule[i]]+late)
			late = time+l[schedule[i]]-d[schedule[i]];
		time+=l[schedule[i]];	
	}
	
	printf("Optimal schedule by greedy algorithm is: ");
	for(i=0;i<n;i++)
		printf("%d, ",schedule[i]+1);
	printf("\nMaximum lateness is %d\n",late);
}

int main()
{
	int n, *l, *d, i;
	printf("Write the number of jobs: ");
	scanf("%d",&n);
	
	l=(int*)malloc(n*sizeof(int));
	d=(int*)malloc(n*sizeof(int));
	
	printf("Write the length of the jobs: ");
	for(i=0;i<n;i++)
		scanf("%d",&l[i]);
	
	printf("Write the deadline of the jobs: ");
	for(i=0;i<n;i++)
		scanf("%d",&d[i]);
		
	schedule_guess(l,d,n);
	schedule_greedy(l,d,n);
	
	return 0;
}