Interval Scheduling Problem with Three Resources

Question

So I am trying to figure out what kind of algorithm I would use if I wanted to implement the ISP with a predefined number of resources. Consider this example interval scheduling problem.

Say there are n requests for a lecture hall and three lecture halls are available to satisfy these requests. Each request has a starting time and an ending time. Create an algorithm to get a maximal scheduling.

I am familiar with the process and I know how the ISP would work if I had only one resource. But how would I apply it in this scenario if I had two, three, or a predefined set of resources.

Any input will be appreciated.

Answer 1

The greedy scheduling with a first fit resource selection is actually not correct. Consider the case where the intervals are:

${ (1, 3) , (2, 5) , (6, 7) , (4, 8) }$,

for simplicity assume we only have 2 resources. The greedy algorithm will assign intervals 1, 2, 3 to resources 1, 2, 1 respectively and will fail to assign a resource for the last interval. Although, a more optimal assignment would have been assigning all 4 of them 1, 2, 2, 1 in the following order.

So another greedy choice has to be made which is the selection of the resource to host the interval. The greedy choice would be selecting the compatible resource with the latest finish time. That way resources which are good (i.e. support more intervals) are kept free.

Intuition to the correctness of the algorithm:

There are 2 claims: 1) Intervals with early finishing time are always better to schedule first.

This is proven by an exchange argument, assume we would leave an interval with early finish time unscheduled to take a later interval, future intervals will definitely have a harder job finding a free room.

2) When an interval is compatible, it is always better to select the worst compatible room.

Since by claim 1, the interval will be taken anyway, the state of the rooms will have a room with $nextFreeTime = endTime_{cur}$ leaving 2 rooms with their previous $nextFreeTime$. Selecting the room with a larger $nextFreeTime$ will leave the better rooms for worse intervals.

Note: The problem can be solved with a less efficient but more obviously correct algorithm using a 3D dynamic programming approach. The state of the dp would indicate the last taken resource in each of the rooms, and the transitions are for each current interval, try selecting all of the compatible rooms updating their states. The intervals are still taken in order of finish time (Claim 1 still holds). The complexity becomes $O(n^3)$, however this is not scalable for k resources unlike the greedy algorithm.

Answer 2

Scheduling could still be done greedily.

Psuedocode:

sort requests by finishing time
list of schedules = [[]]
for each request
    for each schedule in list of schedules
        if request can be appended to schedule
            append and break
    if not appended
        create new schedule
        add request to schedule
        append schedule to list
sort list of schedules by number of requests in each

This should work for any number of requests and 'resources'.