I've been told it is possible to find a solution to this optimization problem in $\Theta(n)$ but I still don't know how I could do it. I did find easily a solution in $n\lg (n)$ though. I only need to have a VALID solution, not the optimal.
This is the problem :
Let say you have n tasks that have a start time and a max time. Each task takes 1 unit of time to complete.
So for example :
T1 = 2,3 T2 = 1,4 T3 = 4,5 T4 = 1,5 T5 = 3,4
This means that T1 CAN be started at time 2 and must be done by time 3. So a correct solution could be :
T2, T1, T5, T3, T4
Any idea on how I could create an algorithm in $\Theta(n)$? For now I thought of using a sorting algorithm that does not use comparison but it only works with integer so I can't really get a reference to an object or something.