1
$\begingroup$

Given $n$ drugs such that each drug $d_i$ should maintain in interval $[c_i,h_i]$.We want to minimize number of containers to maintain medicines in compatible interval.

My answer is as follows:

I use following greedy algorithm:

in each iteration, for remaining drugs, find an interval that have maximum number of compatible drugs, and remove that drugs, and add to container.

any one can help to find an counter example or proving above idea?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
0
$\begingroup$

Here is a counterexample.

There are 6 drugs with intervals $$[1, 5],\ [2,8],\ [3,8]$$ and $$[6, 11], \ [6,12],\ [9, 13].$$

We can use containers of volume 4 to cover the first 3 drugs and containers of volume 10 to cover the last 3 drugs. So it is enough to use 2 kinds of containers.

If we use the greedy algorithm, we would first cover $$[2,8],\ [3,8],\ [6, 11], \ [6,12]$$ using, for example, containers of volume 7. And then the remaining two intervals $$[1,5],\ [9,13]$$ that are disjoint will need additional two containers of different volumes to cover.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Amazing. Thank you, Can give me a hint to find a dynamic programming solution? $\endgroup$
    – user132812
    Mar 16, 2021 at 12:04
  • $\begingroup$ You can check dkaeae's answer to see how we can be correct with a greedy approach. $\endgroup$
    – John L.
    Mar 16, 2021 at 12:05

Your Answer

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