1
$\begingroup$

Possible Duplicate:
How to use greedy algorithm to solve this?

You are given $n$ integers $a_1, \ldots, a_n$ all between $0$ and $l$. Under each integer $a_i$ you should write an integer $b_i$ between $0$ and $l$ with the requirement that the $b_i$'s form a non-decreasing sequence (i.e. $b_i \le b_{i+1}$ for all $i$). Define the deviation of such a sequence to be $\max(|a_1−b_1|,\ldots,|a_n−b_n|)$. Design an algorithm that finds the $b_i$'s with the minimum deviation in runtime $O(n\sqrt[4]{l})$.

There were also two hints, one is to first find an algorithm in $O(nl)$ time, the other is that the runtime of the optimal algorithm is actually must less than $\Theta(n\sqrt[4]{l})$.

I was able to find a solution that runs in $O(n^2)$ (without using any of the hints), but I have no idea how to find an algorithm that runs in $O(n\sqrt[4]{l})$. Can anyone offer some insight into this? Maybe give a rough sketch of your algorithm? Thanks!

$\endgroup$