0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Take jobs that can only be done at time $1, 2, \dots, N$. Permute them and let that be the input. Producing the schedule is now equivalent to sorting the list of jobs so you're not going to do better than the $n\log n$ bound on comparison sorting. $\endgroup$
    – David Richerby
    Nov 21, 2013 at 21:22
  • $\begingroup$ Right. But if we somehow know that all start times and max times are integers in the range $1,2,\dots,m$, then it is possible to sort in $O(m)$ time, so an $O(m)$ time solution may be possible. In particular, if $m=cn$ for some constant $c$, then a $O(n)$ time solution may be possible. Not claiming it will necessarily be faster than just using a standard sort routine..... $\endgroup$
    – D.W. ♦
    Nov 22, 2013 at 19:51

1 Answer 1

Reset to default
1
$\begingroup$

Since there are no dependencies between tasks, you might try a greedy algorithm: at each step, take the task that has the smallest start time (of all remaining tasks), then move on to the next time step. This does end up requiring you to sort.

If the start and end times are all bounded above by some constant times $n$, you might want to read up on non-comparison based sorting routines, such as counting sort. These sorting algorithms can achieve $O(n)$ time (under those conditions), yielding a $O(n)$ time solution to your problem (under the condition that the start and end times are all bounded above by some constant times $n$).

If you have no guarantees on the range of possible start and end times, then as David Richerby explains in his comment, there is no hope of achieving $O(n)$ time: there is a reduction from sorting, as he explains, so $O(n \lg n)$ is about the best you can hope for if we have no guarantees about the start and end times. That still might be plenty efficient in practice; for realistic values of $n$, $\lg n$ will be quite small, and standard sorting algorithms are extremely efficient.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Counting sort etc. are only linear time if the range of values to be sorted is bounded above and below by constants, as you say in your comment to the question. If all the deadlines are in the range $1, \dots, k$ then the following algorithm runs in linear time: output "no" if there are more than $k$ tasks; otherwise, try every permutation of the tasks and output an acceptable one if one exists; output "no" otherwise. $\endgroup$
    – David Richerby
    Nov 22, 2013 at 9:54
  • 1
    $\begingroup$ There are no dependencies between tasks. I'm not sure what you mean exactly by "try every permutation of the tasks". Maybe I don't understand it right but it sounds like a brute-force method that can't really by linear. $\endgroup$
    – user11536
    Nov 22, 2013 at 14:43
  • $\begingroup$ @DavidRicherby, actually, counting sort is helpful if the range of values to be sorted is bounded above by a constant times $n$, i.e., bounded above by $O(n)$ (they don't need to be bounded above by a constant, i.e., by $O(1)$, as you stated). $\endgroup$
    – D.W. ♦
    Nov 22, 2013 at 19:51
  • $\begingroup$ @user11536 Yes, trying every permutation is brute force. However, in my example, the brute force is only used if the number of tasks is bounded by a constant $k$, so even $k! = O(1)$. $\endgroup$
    – David Richerby
    Nov 22, 2013 at 19:55
  • 1
    $\begingroup$ @DavidRicherby, $n$ is not the number of bits of input. Here $n$ is the number of tasks. We haven't been told whether we have any guarantees on the range of start/end times, as a function of $n$ (the number of tasks). I edited my answer to clarify the conditions under which counting sort is helpful. $\endgroup$
    – D.W. ♦
    Nov 22, 2013 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.