I've attended a local programming contest on my country. The name of the contest is "ACM-ICPC Indonesia National Contest 2013".
The contest has ended on 2013-10-13 15:00:00 (GMT +7) and I am still curious about one of the problems.
You can find the original version of the problem here.

Brief Problem Explanation:
There are a set of "jobs" (tasks) that should be performed on several "servers" (computers).
Each job should be executed strictly from start time S_i to end time E_i
Each server can only perform one task at a time.
(The complicated thing goes here) It takes some time for a server to switch from one job to another.
If a server finishes job J_x, then to start job J_y it will need an intermission time T_x,y after job J_x completes. This is the time required by the server to clean up job J_x and load job J_y.
In other word, job J_y can be run after job J_x if and only if E_x + T_x,y = S_y.

The problem is to compute the minimum number of servers needed to do all jobs.

Example:
For example, let there be 3 jobs

S(1) =  3 and E(1) =  6
S(2) = 10 and E(2) = 15
S(3) = 16 and E(3) = 20
T(1,2) = 2,  T(1,3) = 5
T(2,1) = 0,  T(2,3) = 3
T(3,1) = 0,  T(3,2) = 0

In this example, we need 2 servers:

Server 1: J(1), J(2)
Server 2: J(3)

Sample Input:
Short explanation: The first 3 is the number of test cases, following by number of jobs (the second 3 means that there are 3 jobs for case 1), then followed by E_i and S_i, then the T matrix (sized equal with number of jobs).

3
3
3 6
10 15
16 20
0 2 5
0 0 3
0 0 0
4
8 10
4 7
12 15
1 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
4
8 10
4 7
12 15
1 4
0 50 50 50
50 0 50 50
50 50 0 50
50 50 50 0

Sample Output:

Case #1: 2
Case #2: 1
Case #3: 4

Personal Comments:
The time required can be represented as a graph matrix, so I'm supposing this as a directed acyclic graph problem.
Methods I tried so far is brute force and greedy, but got Wrong Answer. (Unfortunately I don't have my code anymore)
Could probably solved by dynamic programming too, but I'm not sure.
I really have no clear idea on how to solve this problem.
So a simple hint or insight will be very helpful to me.