Scheduling Jobs/Intervals in a minimum number of slots
<p>I believe this problem is similar to the Weighted Interval Scheduling problem, but slightly different.</p>

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

<p>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.</p>

<p><a href="http://jsbin.com/bixalabume/1/edit?js,console" rel="nofollow noreferrer">http://jsbin.com/bixalabume/1/edit?js,console</a> (I call intervals "segments".)</p>

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

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

<ul>
<li><a href="https://cs.stackexchange.com/questions/42008/weighted-interval-scheduling-with-m-machines">https://cs.stackexchange.com/questions/42008/weighted-interval-scheduling-with-m-machines</a> - Similar but my problem doesn't have weighted intervals (I think)</li>
<li><a href="https://stackoverflow.com/questions/11143439/appointment-scheduling-algorithm-n-people-with-n-free-busy-slots-constraint-sa">Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)</a> (This is more complicated I believe because it has variable timings for the slots, whereas my slots are equal timings)</li>
</ul>