  Close Menu Navigation

# Interval Scheduling Problem

Let’s consider the Interval Scheduling Problem, in which we have a set of n requests ; the request corresponds to an interval of time starting at and finishing at , or request spans interval . Suppose that a subset of the requests is compatible if no two of them overlap in time; find the largest compatible subset of any set of requests in a reasonable number of steps.

### 1. Algorithm

This is a classical problem used to showcase a class of algorithms known as greedy algorithms. Informally, a greedy solution only seeks to optimize some feature of the problem locally. That is, suppose a greedy algorithms outputs the steps , then invariably, for some function some kind of a measure of how optimal the solution is at each step.

Now, not all “measures of optimality” guarantees global optimality. You need to be careful about what feature of the problem to optimize at each step to ensure that the algorithm will be guaranteed to return an optimum solution. For example, one of the first greedy algorithm that everyone tries on the interval scheduling problem is to just select the next request that starts the earliest. The following illustrates one case under which this strategy will actually work However, using the starting time as a measure of optimality may not work in general, as we could have a really long interval with an early starting time that, as illustrated below, will unfairly mask a sequence of smaller intervals. This may become clearer by arguing that making the current starting time really early does not necessarily mean that fewer intervals can be fitted in.

Similarly, another option to select intervals based on as few incompatibilities will also not be good enough because we can’t also take into account intervals that have already finished by the time that your interval finishes.

Well, you may say, can’t we just filter out the the incompatible intervals based on their finishing time. Yes! This algorithm works, but as it turns out, the fact that we’re minimizing finishing time while minimizing incompatibilities is actually really the same thing as just minimizing that finishing time. This then naturally suggest that selecting the earliest finishing time solves the problem.

function interval_scheduling_problem( ) while is not yet empty
choose a request that has the lowest finishing time delete all requests in that are not compatible with end
return end


We now prove that the above algorithm solves Interval Scheduling.

### 2. Analysis of interval_scheduling_problem

While natural, it is not immediately obvious that this algorithm actually returns an optimal set of compatible intervals. As a start, we first show that the set of intervals returned by the algorithm are at the very least compatible.

#### (Lem 1) The output is a compatible subset of This comes naturally from the fact that we remove all incompatible requests of whenever we add in a request, therefore by definition, is a compatible subset. We now also need to show the optimality of . The idea underlying the proof will be to find a sense in which our greedy algorithm will always “stay ahead” of some other optimal solution . Now, optimistically, we would wish to show that , but this may be too much to ask as there could be more than just one satisfying optimal solution. Instead, we will show that .

Informally, we will compare the partial solutions that our greedy algorithm constructs to the initial segments of , and show that the greedy algorithm is either doing better or at least as well as at each step.

To ease our life, we will consider the following notation within our analysis. Let be the set of requests added into in the order of our algorithm. Similarly, let ordered also by finishing time. Our goal is to prove that .

Let’s probe some properties of first, just to warm up.

#### (Lem 2) is also ordered by starting time

Since is compatible, there are no overlapping intervals, hence the order of the finish time is the same as the order of the starting time. Okay, now let’s show the seemingly natural property that our algorithm always produces the earliest finish time for step when compared to any other solution set similarly ordered.

#### (Lem 3) For all steps , This just stinks of induction doesn’t it? Unsurprisingly, we will show this by induction on .

Let , then it is obvious that . Now, we need to show that .

Suppose that finished at the same time or before , then naturally, will be compatible with because it starts later than , and by . Therefore, because is compatible with , then will finish at least as early as and hence .

This concludes our proof that for all , . Once we have this “stay-ahead” property on the finishing time, the rest becomes trivial.

#### (Thm 4) The greedy algorithm returns an optimal compatible interval

Assume by the way of contradiction that , or that isn’t optimal, then by (Lem 3), we know that . That is, the finish time of is less than the finish time of the first requests of . However, this also means that every one of the last requests in are also compatible with every request of . However, our algorithm explictly guarantees that it will only terminate where there are no more compatible requests, which derives a contradiction. Therefore, the assumption that is incorrect, so it must be the case that its negation, , is true. Now, due to ‘s optimality, , therefore, .

This concludes our proof that our greedy algorithm returns an optimal compatible interval. #### Runtime Analysis

From the two loops both with at most iterations, where is the number of requests, we see that our algorithm runs naively in time.

As an exercise to the reader, it can be shown that this algorithm can be made to run in time . Construct a version of this algorithm

### 3. Lua implementation of interval_scheduling_problem

function compatible(a,b)
local a1,a2 = unpack(a)
local b1,b2 = unpack(b)

return math.max(a1,b1)>=math.min(a2,b2)
end

function interval_scheduling_problem(requests)
local schedule = {}
table.sort(requests, function(a,b)
return a < b
end)

while #requests > 0 do
local i = table.remove(requests,1)
print(unpack(i))
table.insert(schedule, i)

for _,v in ipairs({unpack(requests)}) do
if not compatible(i,v) then
table.remove(requests,_)
end
end
end

return schedule
end


Woosh