-1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Is the question whether your greedy approach works? $\endgroup$
    – Steven
    Commented Sep 17, 2023 at 20:01
  • $\begingroup$ What is your question? We are a Q&A site, so we require you to articulate a specific question (please don't make us guess). Normally, a question ends with a "?". See also cs.stackexchange.com/help/how-to-ask $\endgroup$
    – D.W.
    Commented Sep 18, 2023 at 5:34
  • $\begingroup$ cs.stackexchange.com/q/59964/755 $\endgroup$
    – D.W.
    Commented Sep 18, 2023 at 5:35
  • $\begingroup$ the question is what is the correct approach to solve this problem $\endgroup$
    – John
    Commented Sep 18, 2023 at 13:53

2 Answers 2

0
$\begingroup$

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]$).

$\endgroup$
1
  • $\begingroup$ what would be a correct greedy approach or is this problem's solution even greedy? $\endgroup$
    – John
    Commented Sep 18, 2023 at 13:38
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ it makes sense, thank you very much for your help $\endgroup$
    – John
    Commented Sep 22, 2023 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.