Realizing partitions respecting full and partial order information

For n ∈ N, we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ₁, ..., ℓ_k such that the lengths satisfy a set of simple constraints of the form ℓ_i {white diamond suit}_{i j} ℓ_j where {white diamond suit}_{i j} is one of <, >, or =. In the full information case, {white diamond suit}_{i j} is given for all 1 ≤ i, j ≤ k. In the sequential information case, {white diamond suit}_{i j} is given for all 1 < i < k and j = i ± 1. That is, only the relations between the lengths of consecutive intervals are specified. The cyclic information case is an extension of the sequential information case in which the relationship {white diamond suit}_{1 k} between ℓ₁ and ℓ_k is also given. We show that all three versions of the problem can be solved in time polynomial in k and log n.