// unit-time scheduling with penalties
// see CLR, p. 350-353
#include <stdio.h>
#include <stdlib.h>

typedef struct tableEntry tableType;

struct tableEntry {
  int deadline,penalty;
};

tableType inputTable[500],schedule[500],late[500];

int numTasks,lateTasks=0;

int penaltySort(x,y)
tableType *x,*y;
{
return y->penalty - x->penalty;
}

main()
{
int i,j,totalPenalty=0;

scanf("%d",&numTasks);
for (i=0;i<numTasks;i++)
  scanf("%d %d",&inputTable[i].deadline,&inputTable[i].penalty);
qsort((void*) inputTable,numTasks,sizeof(tableType),penaltySort);
printf("Sorted tasks:\n");
for (i=0;i<numTasks;i++)
  printf("%d %d %d\n",i,inputTable[i].deadline,inputTable[i].penalty);
for (i=0;i<numTasks;i++)
  schedule[i].deadline=999999;
for (i=0;i<numTasks;i++)
{
  printf("Attempting to schedule task with deadline %d penalty %d\n",
    inputTable[i].deadline,inputTable[i].penalty);
  if (schedule[inputTable[i].deadline-1].deadline==999999)
  {
    printf("Found open slot; now search down for earliest possible\n");
    for (j=inputTable[i].deadline-2;
         j>=0 && schedule[j].deadline>=inputTable[i].deadline;
         j--)
      schedule[j+1]=schedule[j];
    schedule[j+1]=inputTable[i];
  }
  else
  {
    for (j=inputTable[i].deadline-1;
         j<i && schedule[j].deadline!=j+1;
         j++)
      ;
    if (j<i)
    {
      printf("Task with deadline %d penalty %d is late\n",
        inputTable[i].deadline,inputTable[i].penalty);
      late[lateTasks++]=inputTable[i];
      continue;
    }
    for (j=i-1;j>=0 && schedule[j].deadline>inputTable[i].deadline;j--)
      schedule[j+1]=schedule[j];
    schedule[j+1]=inputTable[i];
  }
  printf("Schedule is:\n");
  for (j=0;j<i+1-lateTasks;j++)
    printf("%d %d %d\n",j,schedule[j].deadline,schedule[j].penalty);
}
for (i=0;i<lateTasks;i++)
{
  schedule[numTasks-1-i]=late[i];
  totalPenalty+=late[i].penalty;
}
printf("Complete schedule is:\n");
for (i=0;i<numTasks;i++)
  printf("%d %d %d\n",i,schedule[i].deadline,schedule[i].penalty);
printf("total penalty %d\n",totalPenalty);
}