Given m intervals and an array of integers, your task is to minimize the number of operations in which you can make the elements of the array nonposit

Question

You are given the number $m$ and $m$ intervals of the form $a_i, b_i, v_i$, where $a_i<=b_i$ and $v_i>0$ and also a number $n$ and an array $s$ of length $n$, where $s_i>0$. In one operation you can choose an interval say $j$ and decrease the values of $s_i$ by 1, where $a_j<=i<=b_j$, and you can choose interval $j$ at most $v_j$ times. The task is to find the minimum number of operations required to make all elements of $s$ non-positive.

My approach is some greedy where I sort the intervals by the starting point, and then iterate over the values of $s$ and if $s_i$ is positive I repeatedly find the first starting interval that contains index i and apply the minimum necesary ammount of operations. The way I do the update it is with segment trees. Overall, I am not convinced this greedy approach is right.

Answer 1

Your greedy approach does not work. Consider the $m=2$ intervals $[1,2]$ and $[2,3]$ each of which can only be used once. Let the array $s$ of $n = 3$ elements be $\langle 0, 1, 1 \rangle$.

Your approach uses $2$ operations, namely it chooses first the interval $[1,2]$ and then the interval $[2,3]$. However, the minimum number of operations needed to solve the problem is $1$ (i.e., simply choose $[2,3]$).

Answer 2

There is actually a quite simple greedy algorithm that lets us pick one interval after the other in an optimal way. At any point we do the following:

1. Find the smallest i with $s_i > 0$. If there is no such i then we are done. If there is a smallest i, then we need to pick an interval containing i at some point, so we pick it right now.

2. Among all the intervals $[a_j .. b_j]$ with $v_j > 0$ containing i, that is with $a_j ≤ i ≤ b_j$, we pick the one with the largest $b_j$ and remove it, then we go back to Step 1. Removing an interval with a larger $b_j$ is never less good than removing one with a smaller $b_j$, so this will lead to an optimal solution if one exists.

What happens with Steven's counter example against the original algorithm? We have $s_2 > 0$ and $s_3 > 0$. In Step 1 $i = 2$ is the smallest i. Both intervals contain $i = 2$, but for the interval [2 .. 3], $b_j = 3$ has the largest value, so we pick the interval [2 .. 3], decrease $s_2$ and $s_3$, and now we have no i with $s_i > 0$ anymore.