Add Me!Close Menu Navigation

Interval Scheduling Problem

Let’s consider the Interval Scheduling Problem, in which we have a set of n requests \{1,2,\cdots,n\}; the i^{th} request corresponds to an interval of time starting at s_i and finishing at f_i, or request $i$ spans interval $ [s_i,f_i]$. 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 s_1, s_2, s_3, \cdots, c_k, then invariably, V(s_1) \le V(s_2) \le \cdots \le V(s_k) for some function V 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

Rendered by QuickLaTeX.com

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.

Rendered by QuickLaTeX.com

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(requests)
    schedule \gets \{\}
    while requests is not yet empty
        choose a request i_r \in requests that has the lowest finishing time
        schedule \gets schedule \cup \{i_r\}
        delete all requests in requests that are not compatible with i_r
    end
    return schedule
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 schedule is a compatible subset of requests

This comes naturally from the fact that we remove all incompatible requests of schedule whenever we add in a request, therefore by definition, schedule is a compatible subset. \blacksquare

We now also need to show the optimality of schedule. 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 \mathbb O. Now, optimistically, we would wish to show that schedule = \mathbb O, but this may be too much to ask as there could be more than just one satisfying optimal solution. Instead, we will show that |schedule| = |\mathbb{O}|.

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

To ease our life, we will consider the following notation within our analysis. Let i_1, \cdots, i_k be the set of requests added into schedule in the order of our algorithm. Similarly, let \mathbb{O} = \{j_1,\cdots, j_m\} ordered also by finishing time. Our goal is to prove that k=m.

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

(Lem 2) \{j_1,\cdots, j_m\} is also ordered by starting time

Since \mathbb O is compatible, there are no overlapping intervals, hence the order of the finish time is the same as the order of the starting time. \blacksquare

Okay, now let’s show the seemingly natural property that our algorithm always produces the earliest finish time for step k when compared to any other solution set similarly ordered.

(Lem 3) For all steps r \le k, \f{finish}(i_r) \le \f{finish}(j_r)

This just stinks of induction doesn’t it? Unsurprisingly, we will show this by induction on r.

Let P_r \equiv f(i_r) \le f(j_r), then it is obvious that P_1. Now, we need to show that P_{r-1} \implies P_r.

Suppose that i_{r-1} finished at the same time or before j_{r-1}, then naturally, j_r will be compatible with i_1,\cdots,i_{r-1} because it starts later than f(j_{r-1}), and f(j_{r-1}) <= f(i_{r-1}) by P_{n-1}. Therefore, because j_r is compatible with i_1,\cdots,i_{r-1}, then i_r will finish at least as early as f(j_r) and hence P_r.

This concludes our proof that for all r\le k, f(i_r) \le f(j_r). \blacksquare

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 m > k, or that schedule isn’t optimal, then by (Lem 3), we know that f(i_k) \le f(j_k) \le f(j_m). That is, the finish time of schedule is less than the finish time of the first k requests of \mathbb O. However, this also means that every one of the last m-k requests in \mathbb O are also compatible with every request of schedule. 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 m > k is incorrect, so it must be the case that its negation, k \ge m, is true. Now, due to m‘s optimality, k \centernot{>} m, therefore, k = m.

This concludes our proof that our greedy algorithm returns an optimal compatible interval. \blacksquare

Runtime Analysis

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

As an exercise to the reader, it can be shown that this algorithm can be made to run in time O(n \log n). Construct a O(n \log n) 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[2] < b[2]
	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
Posted By Lee

Woosh