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++
Improve this question
$\endgroup$
1
  • $\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$ Commented May 4, 2015 at 17:05

1 Answer 1

Reset to default
3
$\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.

Improve this answer
$\endgroup$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.