Global roundings of sequences

For a given sequence a = (a₁,..., a_n) of numbers, a global rounding is an integer sequence b = (b₁,..., b_n) such that the rounding error | ∑_i∈I(a_i-b _i) | 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(n log n) and generate a global rounding uniformly at random in linear time under a non-degeneracy assumption and in time O(n log n) in the general case.