Interval Partitioning Problem

The interval partitioning problem is described as follows:
Given a set {1, 2, …, n} of n requests, where ith 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}.

Continue reading

Advertisements

Interval Scheduling Problem

The interval scheduling problem is described as follows:

Given a set {1, 2, …, n} of n requests, where ith request starts at time s(i) and finishes at time f(i), find a maximum-size subset of compatible requests. Two requests i and j are compatible if they do not overlap i.e., either f(i) <= s(j) or 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, the maximum-size subset of compatible requests is {1, 3}.

Continue reading