1

I believe this problem is similar to the Weighted Interval Scheduling problem, but slightly different.

Say you have a Shift s that has a start and end time, with the Shift having n slots to fill from s.start to s.end. A slot is a fillable range of time from s.start to s.end. You are given m intervals, where each interval has a start and end time. Assign the intervals to the slots, such that you use the minimum number of slots necessary. An interval can be assigned to a slot as long as there are no overlapping intervals. The given intervals are known to fit in the given number of slots (but they don't have to fill the slots). Once an interval i is assigned to a slot, that slot has been filled for i's time range.

I've written a jsbin that does a brute force algorithm for this, but it is O(n!) or worse, since it checks every possible sequence of intervals and tries to greedily place them into the first slot that has no conflicts.

http://jsbin.com/bixalabume/1/edit?js,console (I call intervals "segments".)

Is this problem solvable in a reasonable amount of time? I feel like there is a DP solution but can't think of one.

I'm not particularly strong in this kind of programming, but here were some similar questions that I looked at but couldn't understand:

Community
  • 1
  • 1
you786
  • 3,659
  • 5
  • 48
  • 74
  • 1
    It's not really clear to me what role the "slots" play, could you explain more about that? – harold Jan 13 '16 at 20:51
  • Say you need two workers from the time the shift starts to the time the shift ends. That is two *slots* to be filled with the given intervals. – you786 Jan 13 '16 at 21:19
  • Ok so if I understand this correctly, this is graph coloring on an interval graph? – harold Jan 13 '16 at 21:34
  • I'm not too familiar with interval graphs, but yes it does look similar. At most there should be *m* edges between each vertex/interval where *m* is the number of shift slots. I'm not sure if graph coloring applies here, although the wikipedia article on interval graphs seems to have a similar note about resource allocation. – you786 Jan 14 '16 at 14:44
  • The colors would correspond to slots, vertexes to intervals, edges to overlap over intervals. As the article mentions, the colors can be computed in polynomial time by just inserting them at the first slot they can go in, when ordered by start time. – harold Jan 14 '16 at 14:50
  • @harold Thank you! I just read up more about graph coloring on an interval and did the same. Please make an answer so I can accept it! – you786 Jan 14 '16 at 15:05

1 Answers1

2

This can be solved with graph colouring, where for every interval you make a vertex, and a vertex has links with an other vertex iff the corresponding intervals overlap. That automatically makes the interference graph an interval graph, which is very easy to colour, without even constructing the graph: sort the intervals by starting time and insert them one by one in the first slot that they can go into. This will be optimal because in order to require a new colour k when inserting, it must be the case that k - 1 colours were occupied at the starting time of the interval being inserted, so at least k intervals overlap at that time so they couldn't have been given fewer than k colours anyway.

harold
  • 61,398
  • 6
  • 86
  • 164