0
$\begingroup$

I am writing a greedy algorithm for a variation of the interval scheduling problem that I haven't seen before.

I have a set of jobs, each with start and finish time. All jobs in set must be assigned to a worker, workers cannot have overlapping jobs. My greedy algorithm should minimise workers - use the least number of workers possible to complete all jobs.

Does this algorithm accomplish this? It seems too simple to me and I have probably neglected to think of something.

sort(jobs) //earliest starting time first

w = 0 //number of allocated workers

for i = 1 to n {
    if (worker w has no job with finish time later than starting time of job i)
        schedule(worker w, job i)
    else
        schedule(worker w+1, job i)
        w++
$\endgroup$
  • $\begingroup$ What have you tried? We expect you to make a significant effort before asking: e.g., to search/research whether this has been studied before. In your case, you want to know whether a particular algorithm gives the optimal answer: well, have you tried running on your algorithm on a bunch of test cases to see whether it gives the optimal answer on all of them? That's usually the first step in checking whether a greedy algorithm might plausibly work. $\endgroup$ – D.W. May 4 '15 at 17:05
2
$\begingroup$

This is called Interval Partitioning Problem or Interval Coloring Problem in this lecture note, as well as in Section 4.1 of the book [1].

Given intervals $(s_i, f_i)$, assign them to processors/workers so that you schedule every interval and use the smallest number of processors/workers.

The greedy algorithm is a simple one-pass strategy that orders intervals by their starting times, goes through the intervals in this order, and tries to assign to each interval it encounters a processor/worker that has not already been assigned to any previous interval that overlaps it.


[1] Algorithm Design. By Jon Kleinberg and Eva Tardos.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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