Consider the following problem $Q$: We are given an integer $n$, and $k$ intervals $[l_i,r_i]$ with $1\leq l_i\leq r_i\leq 2n$. We are also given $2n$ integers $d_1,…,d_{2n}\geq 0$. The task is to select a minimum number of intervals $[l_i,r_i]$ such that for every $i=1,…,2n$, at least $d_i$ intervals containing the integer $i$ are selected.
It is not hard to see that $Q$ can be solved in polynomial time (see below).
Now consider the following slightly modified problem $Q’$: The input of the problem is the same as before. However, the task now is to select a minimum number of intervals such that for every $i=1,…,n$, at least $d_{2i-1}$ intervals containing the integer $2i-1$ or at least $d_{2i}$ intervals containing the integer $2i$ are selected (with “or” we mean the usual logical or).
My question: Can $Q’$ be solved in polynomial time?
Here are two ways to solve $Q$ efficiently:
A simple greedy algorithm: Sweep through the intervals from left-to-right and select only as few intervals as are necessary to “satisfy” the numbers $d_i$. Whenever there is a choice between different intervals, choose the one(s) with maximal right endpoint.
An integer program: For each interval $[l_i,r_i]$ introduce a decision variable $x_i\in\{0,1\}$ with $x_i=1$ iff the interval is selected. The objective is to minimize $ x_1+…+x_k$, subject to the constraints $\sum_{j:i\in[l_j,r_j]} x_j\geq d_i$. The constraint matrix of this integer program has the consecutive ones property and therefore the linear programming relaxation of this program has an integer optimal solution.
Thanks for any hints, and also for references!
