Interval Partitioning Problem

The interval partitioning problem is described as follows:
Given a set {1, 2, …, n} of n requests, where i^th request starts at time s(i) and finishes at time f(i), find the minimum number of resources needed to schedule all requests so that no two requests are assigned to the same resource at the same time. Two requests i and j can conflict in one of two ways:

1. s(i) <= s(j) and f(i) > s(j)
2. s(j) <= s(i) and f(j) > s(i)

Example: Given 3 requests with s(1) = 1, f(1) = 3, s(2) = 2, f(2) = 4, s(3) = 3, f(3) = 5, at least 2 resources are needed to satisfy all requests. A valid assignment of requests to resources is {1, 3} and {2}.

This problem can be solved optimally with a greedy strategy of scheduling requests based on earliest start time i.e., from the set of remaining requests, we always select the one with the earliest start time and assign it to one of the available resources (if it would not cause a conflict) or demand another resource for this request.

Algorithm:

	Let R be the set of all requests
	Let d = 0 be the number of resources
	while !R.empty():
	Choose a request i ∈ R that has the earliest start time
	if i can be assigned to some resource k <= d:
	assign request i to resource k
	else:
	allocate a new resource d+1
	assign request i to resource d+1
	d = d + 1
	return d

view raw Interval Partitioning Problem.py hosted with ❤ by GitHub

Proof of optimality:

Let us define the depth of a set of requests R to be the maximum number of requests in R in conflict at any time. It is clear that for any set of requests R, the number of resources required is at least the depth of R because the requests in conflict must be assigned to different resources.

We now prove by contradiction that the above greedy algorithm uses exactly d resources to schedule a set of requests R, where d is the depth of the set R.

Suppose the greedy algorithm uses more than d resources. Let j be the first request that is assigned to the resource d+1. Since we process requests according to non-decreasing start times, there are d requests that start (at or) before j and are in conflict with j. Thus at the start time of request j, there are at least d+1 requests in conflict, contradicting our assumption that the depth is d. Thus, the greedy algorithm uses exactly d resources and hence is optimal.

Implementation and Running time:

The algorithm can be implemented in O(n log n + n log d) = O(n log n) by pre-sorting the n requests in order of start time and using an Indexed min-priority queue to keep track of the resource having the earliest free time (the time at which the resource becomes free).

	sort the n requests in order of start time
	d = 1
	assign request 1 to resource 1
	min_pq.insert(1, f(i))
	for i = 2 to n:
	j = min_pq.minIndex()
	if s(i) >= min_pq.keyOf(j):
	assign request i to resource j
	min_pq.increaseKey(j, f(i))
	else:
	d += 1
	assign request i to resource d
	min_pq.insert(d, f(i))
	return d

view raw Interval Partitioning Problem Implementation.py hosted with ❤ by GitHub

The initial sorting of requests take O(n log n) time. Then, for each request, we either increase key of a resource or insert a new resource in the priority queue at the time when the priority queue contains d resources, each of which take O(log d) time. Thus the overall time complexity is (n log n + n log d) = O(n log n), i.e., the time to sort dominates the overall running time of the algorithm.

Take a look at C++ implementation.

Try your hand at problem DONALDO which uses this idea.

Reference: Algorithm Design by Kleinberg and Tardos