Suppose you have a collection of sets of integers from the range [1,n]. Then the question "Can you cover all of [1,n] by choosing one integer from each set?" is answered by Hall's Marriage Theorem -- yes, provided any size k subset of [1,n] intersects at least k of the sets in my collection. Moreover it is computationally efficient to make an actual choice of which integer to use from each set, or to list all the possible choice functions: the proof of Hall's is essentially an argument that if you pick one a a time without doing anything stupid, you never need to backtrack. What if instead you start with a collection of sets of *intervals of integers* in [1,n]? I want to know whether it's possible to pick one interval from each set in such a way that their union is all of [1,n]. And if so, I'd like to know the same constructiveness facts: can I find one or all such assignments efficiently? The full generalization, of course, is where you start with a collection of sets of *subsets* of [1,n]. But without thinking about it much at all, it seems overwhelmingly likely to me that this will turn out to be NP-complete. So the question is, does restricting to intervals tame the situation enough to make it feasible? --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.