An algorithm for creating a matrix with certain properties

Question

I'm searching for an algorithm that efficiently does the following

Input:

• $n\in \mathbb{N}$
• $j_1,j_2,\ldots ,j_n$ with the property $j_1<j_2<\cdots<j_n$
• $b_1,\ldots ,b_n \in \mathbb{N}$
• $m\geq b_1+\cdots+b_n$

Output: a Matrix of $n\times m$ with the property described bellow:
To be more precise, I have a special case of an $n\times m$ matrix ($n$ is given, $m$ has a bounded lower value equal to $b_1+b_2+\cdots+b_n$ but we can choose it to be arbitrary large if we like).

We are also given a series of coordinates $j_1<\cdots<j_n$ that each defines a position in line 1,2 etc. For example if $j_1=3$ then the postion $(1,3)$ of the matrix. Matrix elements are 0 or 1 under the constrain that each column can have at most one 1 and each line $i$ exactly $b_i$ 1s.

From all the possible matrices we're interested in finding one ( one certainly exists) that has the the following property:

$\max\{|j_k-\mathrm{positionOf}(1)|, k= 1,\ldots,n$ and for all 1 appearing on each of the $i_k$ line$\}$ is the lowest of all the other possible matrices. Less formal, I want to find one of the matrices that minimizes the biggest distance of '1' from $j_k$ for all $j_k$.

Is there an algorithm (preferably of linear complexity) to find such an array? My best effort so far solves it in polynomial time but it's really a brute force solution and not very applicable.

Thank you in advance.

Answer 1

Algorithm for searching the best value of max distance from $j_k$ to 1

dist = -1
repeat
  dist = dist + 1
  pos = -infinity
  success = true
  for k = 1 to n 
    pos = max(pos, j[k] - dist)
    pos = pos + b[k]
    if pos > j[k] + dist + 1 then
      success = false
      terminate the execution of "for" loop
    end-if
  end-for
until success
print(dist)