インターバル保存要求を処理するスタック

An interval storage request is represented by a tuple \$(s,t,v)\$
satisfying \$s

The question is: given a set of interval storage requests and
capacitated machines, what is the largest subset (in cardinality)
of the requests such that we can find a way to serve them using the
given stacks (when a request come, we can decide which stack to
push it in)?

The formal statement of the problem is the following. We say two
intervals \$[s_i,t_i]\$ and \$[s_j,t_j]\$ cross if \$s_1

Given intervals \$I={[s_i,t_i]}_{iin [n]}\$ (assume all
endpoints are different integers in \$[2n]\$), together with integer
\$T\$ and \${m_t}_{tin [T]}\$, find a collection of disjoint subsets
\$J_1,cdots, J_Tsubseteq [n]\$ with the largest sum of
cardinalities \$|J_1|+cdots+|J_T|\$ such that:

(i) (no crossing) for any \$tin [T]\$, no two intervals in
\$I_{J_t}={[s_i,t_i]mid iin J_t}\$ cross;

(ii) (capacity constraint) for any \$tin [T]\$, there is no
integer \$kin [2n]\$ such that \$k\$ is contained in at least \$m_t+1\$
intervals in \$I_{J_t}\$.

The case \$T=1\$ is easy. Some other interesting special cases
include:

(a) \$forall iin [T], m_i=infty.\$ Namely, there is no capacity
constraint.

(b) Determine whether or not all requests can be served.

I wonder if this problem (or any of the above special cases) was
studied before? Any previous results or new ideas are
appreciated.

ベストアンサー