I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements:

  • The element 1 is in position 1, and element N must be at a position >= the position of element N-1. (i.e. element 2 could be at position 1, element 3 at position 7, and element 4 at position 8 (but not position 5))
  • Some elements must be within a certain distance from each other on the line.
  • Some elements must be at least a certain distance from other on the line.

My objective is to return an integer that represents the maximum span between element 1 and element N. If no lineup is possible, return -1, and if the elements can be any distance apart, return -2.

I am given:

  • The number of elements
  • A withinArray[][] where withinArray[x][y] = the distance elements x and y must be within on the line. Any zero values represent no constraints.
  • An atLeastArray[][] where atLeastArray[x][y] = the distance elements x and y must be apart on the line. Any zero values represent no constraints.

An example input would be: 4 elements, withinArray1[3] = 10, withinArray[2][4] = 20, and atLeastArray[2][3] = 3. (all other array values are zero).

The return value for this input would be 27. (element 1 at position 1, element 2 at position 8, element 3 at position 11, and element 4 at position 28)

The problem was first posted here by someone else. I'd like to figure out an elegant solution to it programmatically. Though I've been working on it for a whole day, I still have no luck coming up with a good solution. I feel that I need to use dynamic programming techniques, but have a hard time finding a good substructure.

I am not able to locate the same example on the web. Any pointer to such materials online would be appreciated. It's even better if you are an expert for such kind of question and can outline the solution in detail. Executable code is a plus.

EDIT: I know how to formulate this as a linear programming problem and I know how to solve it using LP solver. I just prefer an end-to-end solution with input and output as specified. General answers might not help me much.

  • 1
    $\begingroup$ Is there a particular reason a standard LP solver won't work? It really feels like there should be a constructive algorithm to this problem, but that doesn't mean it can't be solved in the usual way. $\endgroup$ Dec 7 '12 at 20:15

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.