import java.util.*;

public class UnitTasks
{
  public static void main(String[] args)
  {
    //********** Generating random tasks
    int n = (int)Math.round(Math.random()*10) + 5;     // # of tasks
    UnitTask[] tasks = new UnitTask[n];
    for (int i=0; i<n; i++)
    {
      int deadline = (int)Math.round(Math.random()*n) + 1;
      int penalty = (int)Math.round(Math.random()*100);
      tasks[i] = new UnitTask(deadline, penalty, (i+1));
    }
    System.out.println("Original tasks:");
    printTasks(tasks);

    //********** Sorting tasks
    Comparator<UnitTask> c1 = new Comparator<UnitTask>()
    {
      public int compare(UnitTask t1, UnitTask t2)
      {
        int penalty1 = t1.penalty;
        int penalty2 = t2.penalty;
        if (penalty1 > penalty2) return(-1);
        else if (penalty1 < penalty2) return(1);
        else 
          return(0);
      }
    };
    Arrays.sort(tasks, c1);
    System.out.println("\nStep I: sorting tasks by penalty");
    printTasks(tasks);

    //********** STEP 1: Composing list of tasks
    System.out.println("\nStep II: composing optimal list of early tasks");
    ArrayList<UnitTask> scheduleE = new ArrayList<UnitTask>();  // early tasks
    ArrayList<UnitTask> scheduleL = new ArrayList<UnitTask>();  // late tasks
    int[] N = new int[n+1];                  // this is N_t(A) in text
    for (int i=0; i<n; i++)
    {
      System.out.println("Checking task a_" + tasks[i].index + ":");
      for (int j=1; j<=n; j++)               // update the N_t function
      {
        if (tasks[i].deadline <= j)  
          N[j]++;    
        System.out.print("N" + j + "=" + N[j] + "  ");
      }

      boolean accept = true;                 // check if the sset of indep.
      for (int j=1; j<=n; j++)               // can be extended by adding
        if (N[j] > j)                        // a_i
        {
          accept = false;
          for (int k=1; k<=n; k++)
            if (tasks[i].deadline >= k)
              N[k]--;
        }

      if (accept)
      {                                      // can be extended
        scheduleE.add(tasks[i]);             // if yes - pick this task
        System.out.println("\naccept\n");
      }    
      else                                   // otherwise it will be
      {
        scheduleL.add(tasks[i]);             // processed late
        System.out.println("\nskip\n");
      }
    }
    System.out.println("Optimal set of early tasks:");
    for (int i=0; i<scheduleE.size(); i++)
      System.out.print("a" + scheduleE.get(i).index + " ");
    System.out.println();

    System.out.println("\nStep III: sorting early tasks on deadlines");
    int k = 0;                               // convert the tasks into array
    UnitTask[] scheduleA = new UnitTask[scheduleE.size()];
    for (Iterator<UnitTask> it=scheduleE.iterator(); it.hasNext(); )
      scheduleA[k++] = it.next();

    //********** STEP 2: Sorting selected tasks by the deadlines
    Comparator<UnitTask> c2 = new Comparator<UnitTask>()
    {
      public int compare(UnitTask t1, UnitTask t2)
      {
        int deadline1 = t1.deadline;
        int deadline2 = t2.deadline;
        if (deadline1 < deadline2) return(-1);
        else if (deadline1 > deadline2) return(1);
        else
          return(0);
      }
    };
    Arrays.sort(scheduleA, c2);
    printSchedule(scheduleA, scheduleL);
  }

  public static void printTasks(UnitTask[] tasks)
  {
    int n = tasks.length;
    System.out.print("Task:      ");
    for (int i=0; i<n; i++)
      System.out.printf("a%-3d", tasks[i].index);
    System.out.print("\nDeadline:  ");
    for (int i=0; i<n; i++)
      System.out.printf("%-4d", tasks[i].deadline);
    System.out.print("\nPenalty:   ");
    for (int i=0; i<n; i++)
      System.out.printf("%-4d", tasks[i].penalty);
    System.out.println();
  }
  
  public static void printSchedule(UnitTask[] tasks, ArrayList<UnitTask> al)
  {
    System.out.println("Optimal schedule:  (early tasks)  (late tasks)");
    System.out.print("(");
    for (int i=0; i<tasks.length; i++)
      if (i==0)
        System.out.print("a" + tasks[i].index);
      else
        System.out.print(" a" + tasks[i].index);
    System.out.print(")  (");
    int penalty = 0;
    for (Iterator<UnitTask> it=al.iterator(); it.hasNext(); )
    {
      UnitTask t = it.next();
      if (it.hasNext())
        System.out.print("a" + t.index + " ");
      else
        System.out.print("a" + t.index);
      penalty += t.penalty;
    }
    System.out.println(")");
    System.out.println("Penalty = " + penalty);
  }
}

class UnitTask
{
  public int deadline;
  public int penalty;
  public int index;
  public UnitTask(int deadline, int penalty, int index)
  {
    this.deadline = deadline;
    this.penalty = penalty;
    this.index = index;
  }
}