CareerCup

A service system has n DIFFERENT servers; each one provides one unique service to the clients. Clients submit requests to the service system, each request may have multiple sub-requests; each sub-request is to a DIFFERENT server. A request can have at most n sub-requests. Each sub-request takes 1 time unit to finish at any server. The finish time of a request is the finish time of its LAST finished sub-request. The notation "total request finish time" is the sum of all requests' finish time.

1. Design an off-line algorithm to reorder the execution order of sub-requests on the servers, so that "total request finish time" can be minimized (if multiple solutions exist, only one solution is enough). Discuss the complexity of the algorithm.

Input format:
Line 1: number of requests.
Line 2: number of servers in the system, n.
Line 3 to (n+2): sub-requests (denoted with their parent requests’ IDs) at each server, the i’th line represents the sub-requests to be served at server ID = (i-2).
Output format:
Line 1 to (n-1): the execution order of sub-requests, so that “total request finish time” can be minimized.

Sample input 1:
4
4
1 2 3 4
3 2 1 4
4 2 1 3
2 3 4 1

Sample output 1:
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4

(The “total request finish time” of input is 14; and output is 10).


Sample Input 2:
6
6
1 6 2
4 3 5 1
1 2
1 2 4 6
3
5 6

Sample Output 2:
6 1 2
3 1 4 5
1 2
6 1 4 2
3
6 5

(The “total request finish time” of input is 19; and output is 15).

2. Discuss feasible algorithms that can achieve sub-optimal solutions with N ~ 10000.

3. Suppose the sub-requests can be queued at each server, and the servers are running all the time. Discuss feasible on-line algorithms that can achieve sub-optimal solutions with N ~ 10000.