TCHS-8-1000

Problem Statement

When scheduling tasks to be executed by a person, it is sometimes the case that when one task is completed, a later task suddenly becomes more important. In these situations, it is said that the later task is a 'Supertask' of the completed one.

In addition, when a task reaches a certain level of importance, it must be executed immediately. Each task is initially given a priority of 0. Whenever a task is completed, the priority of its Supertask increases by 1. If at some moment one of the tasks has a priority of 2, and has not been previously executed, it must be executed immediately. If no remaining task has a priority of 2, a single unexecuted task of your choice must be executed (you can not wait and must execute one of them).

You have been given N tasks (referenced by numbers 0 to N-1) that must be executed. All of these tasks (with the exception of the last) have a single Supertask, and you are guaranteed that the reference number of a task will always be lower than the reference number of its Supertask. The last task has no supertask, instead the number -1 is used. You also wish to execute the last task (with reference number N-1) as late as possible. Every task takes one minute to complete execution. Given the supertasks for each task, return the latest time (in minutes) that the last task can be started, if you start executing tasks at time 0.

You will be given the supertasks as a int[] supertasks, where element i of supertasks contains the reference number of the supertask for task i.

Definition

Class:	PendingTasks
Method:	latestProcess
Parameters:	int[]
Returns:	int
Method signature:	int latestProcess(int[] supertasks)
(be sure your method is public)

Notes

-

If a task is executed after its Supertask, then its execution has no bearing on the priority of the Supertask.

-

Tasks can only be executed once

Constraints

-

supertasks will contain between 1 and 50 elements, inclusive

-

Element i of supertasks will be between i + 1 and (number of elements in supertasks - 1), inclusive, except the last element of supertasks, which will be -1.

Examples

0)

{4,4,4,4,-1}

Returns: 2

The final task is a supertask of all other tasks. Whenever you finish any two of first four tasks, the priority of the last will have risen from 0 to 2, so it must execute immediately. This happens after two tasks, so the latest it can start is after two minutes.

1)

{1,2,3,4,-1}

Returns: 4

You can do the tasks in order, putting the final task last, starting it at the fourth minute.

2)

{-1}

Returns: 0

The final task is also the only task, so it must be executed immediately.

3)

{6,6,6,7,7,7,8,8,-1}

Returns: 7

We have the following tree:

      8
   /     \
  6       7
/ | \   / | \
0 1 2   3 4 5

We can not complete all of tasks 0 to 7 before task 8 because:
a) one of tasks 0, 1, 2 must be completed after task 6.
b) one of tasks 3, 4, 5 must be completed after task 7.
c) task 8 must be started as soon as both 6 and 7 are finished - so one of 0 to 5 will not be completed at that moment.
One of the possible orderings which starts the final task at the 7th minute is the following: 0, 1, 6, 2, 3, 4, 7, 8.

import static java.lang.Math.max;
import java.util.*;

public class PendingTasks {

	final int N = 60;
	int[][] dp = new int[N][3];
	List<Integer>[] g = new ArrayList[N];
	int n;
	
	public int latestProcess(int[] parents) {
		n = parents.length;
		for (int i = 0; i < n; i++)
			g[i] = new ArrayList<Integer>();
		for (int i = 0; i < n - 1; i++)
			g[parents[i]].add(i);
		for (int i = 0; i < n; i++) {
			int sum = 0, dist = 0;
			for (int j = 0; j < g[i].size(); j++) {
				int u = g[i].get(j);
				sum += dp[u][0];
				dist = max(dist, dp[u][2] - dp[u][0]);
			}
			dp[i][0] = sum + dist;
			dist = 0;
			dp[i][1] = sum + 1;
			for (int j = 0; j < g[i].size(); j++) {
				int u = g[i].get(j);
				dist = max(dist, dp[u][2] - dp[u][0]);
				for (int k = 0; k < g[i].size(); k++)
					if (k != j) {
						int v = g[i].get(k);
						dist = max(dist, dp[u][2]-dp[u][0]+dp[v][1]-dp[v][0]);
					}
			}
			dp[i][1] += dist;
			dp[i][2] = 1;
			for (int j = 0; j < g[i].size(); j++) {
				int u = g[i].get(j);
				dp[i][2] += dp[u][2];
			}
		}
		return dp[n-1][1] - 1;
	}
	
}