I don't understand what the question is asking. Do you have the same feeling?

The problem statement is missing clearity.

*With the first three tasks, the optimal schedule can be: time 1 : task 2 time 2 : task 1 time 3 : task 3 time 4 : task 1 time 5 : task 3 time 6 : task 3

Task 1 has a deadline 2, and it finishes at time 4. So it exceeds its deadline by 2. Task 2 has a deadline 1, and it finishes at time 1. So it exceeds its deadline by 0. Task 3 has a deadline 4, and it finishes at time 6. So it exceeds its deadline by 2.

Thus, the maximum time by which you overshoot a deadline is 2. No schedule can do better than this.*

I percieve it would be best to: time 1 : task 2 time 2 : task 1 time 3 : task 1 time 4 : task 3 time 5 : task 3 time 6 : task 3

and have output: 1 0 2

An important and nontrivial part of the problem specification is buried in the "output format" section. This is not a great idea, the initial part of the problem statement, before the I/O formats and constraints, should specify the conceptual part of the problem completely.

Oh joy, I solved the wrong problem! Should have read the output requirement and the sample example more clearly.

I solved the problem to: "Minimize the maximum amount of overshoot, when all tasks are scheduled." i.e. if 5 tasks were scheduled with overshoots O1 O2 O3 O4 O5, schedule them such that the max(O1, O2, O3, O4, O5) is minimized. Sad face.

Solved with a simple sorted list of deadlines. First key was to realize all tasks have to be completed in order of deadline, there is no better way to do it to minimize the time a deadline has been missed.

I failed tests 5-9 due to timeout until I realized that when I have a task that goes over by the maximum amount of any task in my list, I don't care about any tasks with deadlines before that ever. In the example:

2 2 
# task 1 is not late, 0

1 1
# task 2 is earlier so it goes first and is on time,
# task 1 is not late by 1 (the max), so I no longer
# care about task 2

4 3
# task 2 is late by 1 (3 units of work done), task 3 here
# is now late by 2 (6 units of work done), so I no longer
# care about task 2

10 1
# task 3 is late by 1 still, at deadline 10 I have
# task 4 that has 7 units of work before it and isn't late

2 1
# since task 3's deadline is later, I just add the work
# to all the deadlines remaining, meaning

My Submission I think could fail under certain test cases so I think there must be a better way. The worst case would be 99,999 tasks in order with D_i of index + 1 and M_i of 1. I think I could solve that though. Maybe there should be a tougher problem set like that? How did other people solve it?