I have $n$ items arranged on a straight line (like a number line, items can only move 2 directions). The each item has a size, some distance around their center position, that can't overlap with other items. They also cannot cross each other.

The problem:

We have a set $S$ of positions (of size $\leq n$). We need to find a way to move the items, so that after the movement each position in $S$ has one item there. (There might be other items at other positions as well.) The goal is to minimize the total movement of all items. Is there an efficient algorithm to find the way to move the objects that minimizes this?

  • $\begingroup$ This is a nice exercise. What approaches have you tried? Have you tried greedy algorithms? divide-and-conquer? dynamic programming? If not, try each one. I will tell you that you can find a solution using at least one of those three methods. I'll let you have the joy of discovering the details of how for yourself. $\endgroup$
    – D.W.
    Jun 5, 2018 at 0:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.