Subscribe to the weekly news from TrueShelf


Task assignment using Hall's Theorem

You are given a collection of tasks each of which must be assigned a time slot in the range {\(1,\dots,n\)}. Each task \(j\) has an associated interval \(I_j = [s_j,t_j]\) and the time slot assigned to \(j\) must fall in the interval \(I_j\). Each time slot can be assigned to at most one task. Show that it is possible to assign time slots to tasks satisfying these constraints if and only if the following condition holds:

For any integers \(x,y\) with \(1 \leq x \leq y \leq n\), the number of intervals \(I_j\) contained in \([x,y]\) is at most \(y-x+1\).

Hint : Use Hall's Theorem.

Related Content