Global roundings of sequences

For a given sequence a=(a₁,…,an) of numbers, a global rounding is an integer sequence b=(b₁,…,bn) such that the rounding error |_∑i∈I(ai−bi)| is less than one in all intervals I⊆{1,…,n}. We give a simple characterization of the set of global roundings of a. This allows to compute optimal roundings in time O(nlogn) and generate a global rounding uniformly at random in linear time under a non-degeneracy assumption and in time O(nlogn) in the general case.