# 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:*

- s(i) <= s(j) and f(i) > s(j)
- 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}.

View original post 390 more words

Posted on September 30, 2013, in Algorithms and tagged Interval Partitioning Problem. Bookmark the permalink. Leave a comment.

## Leave a comment

## Comments 0