Assume that we have a set system $\mathfrak T = \{\mathcal T\_1, \mathcal T\_2, \dots, \mathcal T\_N \}$ where each $\mathcal T\_k$ is a collection of subsets of $[n] := \{1,\dots,n\}$ of the form 
$$ \mathcal T\_k = [m\_k, M\_k] := \{T \subseteq [n]:\; m\_k \subseteq T \subseteq M\_k \}. $$
Moreover, we know that $\mathcal T\_k$s are mutually disjoint, i.e., $\mathcal T\_k \cap \mathcal T\_{k'} = \emptyset$ when $k \neq k'$, which implies that $N \le 2^n$. Note also that $\mathcal T\_k \subseteq 2^{[n]}$ for each $k$.


Question: Is there an algorithm with polynomial time in $(N,n)$ to either find a subset in $2^{[n]}$ which is not in any of the $\mathcal T\_k$s when possible, otherwise conclude that $\bigcup \mathfrak T := \bigcup\_{k=1}^N \mathcal T\_k = 2^{[n]}$, i.e. the set system covers the power set?


EDIT: Changed the number of subsets to $N$ instead of $m$. Corrected the question from polynomial time in $n$ to polynomial time in $(N,n)$. Also, fixed the statement regarding the union of elements of $\mathfrak T$. There were many confused statements in the original post. Hopefully, this version is clear. The problem is to see if we can cover the power set, not the ground set $[n]$. That is, all the action is at the level of subsets of $[n]$. 



Algorithm to decide if the union of a set system covers the power set
Given $T\_k = [m\_k,M\_k]$ and $X\subseteq [n]$, it is easy to calculate the number of sets in $T\_k$ that contain $X$: $$Q\_{X,k}=|\{T\in T\_k \mid X\subseteq T\rbrace|.$$


So start with $\sum\_k Q\_{\emptyset,k}$. If it equals $2^n$, every subset of $[n]$ is covered.


Otherwise, there is $x\_1\in [n]$ such that $\sum\_k Q\_{\lbrace x\_1\rbrace,k} \lt 2^{n-1}$; find it by trying the $n$ cases. Then find $x\_2$ such that $\sum\_k Q\_{\lbrace x\_1,x\_2\rbrace,k} \lt 2^{n-2}$ by trying all cases for $x\_2$. Continuing in this manner, after at most $n$ rounds you will have $X\subseteq [n]$ such that $\sum\_k Q\_{X,k}=0$.


Altogether it seems to need something like $O(n^2N)$ operations on sets.


