11358 - Faster Processing Feasibility

[sclo]

I tried solving this problem using a greedy method, but get WA. How did other people solved this problem?
My greedy choice is to always process the available jobs with sooner deadlines first.

I now have a feeling that earliest deadline first is not optimal for multiprocessor case. It is optimal only for single processor case.

[sohel]

The judge solution was written using 'network flow' with (3*T + 2) nodes under consideration.

But there is a greedy solution.

[sclo]

I thought that it was NP-hard problem, so greedy doesn't work.
I tried network flow, and it is correct.

This problem is actually almost exactly like 11167 - Monkeys in the Emei Mountain, except the output is easier here. It was decided that greedy was incorrect for that problem, so greedy shouldn't be correct for this problem either.

All it takes to break my greedy method is to use:

Code: Select all

2 3
0 1 1
0 1 2
0 3 3

Earliest deadline will return "NO WAY" but the answer is "FEASIBLE"

[little joey]

You base your greedy on earliest deadline, but that's not the correct criterion. My greedy answers "FEASIBLE" for your input. Can't remember all the details of the monkeys problem, but I think greedy is correct for this problem.

[Adrian Kuegel]

The greedy is actually quite easy: Process those tasks first which have smallest difference "time to deadline" - "remaining processing time needed". I think it should be correct.

[shanto86]

i did as adrian said during onsite and got AC

[sclo]

How about this case?

Code: Select all

2 5
0 1 1
2 2 4
2 2 4
0 1 2
0 2 4

According to your greedy: At time 0, you would schedule task 0 and 3. At time 1, only task 4 is available and one of the processor is idle, so the whole schedule is not feasible.
The correct solution is to schedule task 0 and 4 at time 0.

[little joey]

You're right, my greedy gives "NO WAY"

[Kraken]

I'm doing max flow using ford-fulkerson and getting TLE because of the fact that i have to clear a 2-dimensional capacity array of size 100 million in each test case.

Is there a better way than having 1 node for each possible time (to decrease number of nodes)?