Random placement of non-overlapping intervals

Question

I have an interval G, and a set of non-overlapping sub-intervals of various lengths s₁, s₂, ..., s_n.

G |--------------------------------------------------------------// //-----------|
        s1 [---]                       s3 [------------------]
                    s2 [------]                                         sn [--]     

I'm looking for an algorithm for taking all of these sub-intervals and then placing them again on G randomly, such that they don't overlap. What is the best way to do this?

The easiest, most naive approach would be simply to randomly select starting positions for each subinterval, check for overlaps once all intervals are placed, and then start over if there are overlaps. This would probably be pretty fast if the sub-intervals provide sparse coverage of G, but increasingly inefficient as density increases.

A similar idea is to check for overlap as each sub-interval is placed. Similar concerns about efficiency though.

Is there any more clever way of handling this?

UPDATE

To clarify a couple of points:

• It is the spacing of the sub-intervals that I would like randomly distributed.
• The uniform distribution is probably the most appropriate concept of randomness in this case.
• These are discrete (integer) closed intervals, not continuous.

Answer 1

I think okio's answer will give a biased distribution of the gaps (i.e. the first gaps will tend to be larger then later gaps.

However, I think a very similar approach should work better:

1. Shrink all sn to zero length
2. Choose random positions for each sn in lenG-lenS
3. Expand sn back to their original lengths

Answer 2

Something like this ?

lenG = length(G)
lenS = length(s1) + length(s2) + length(s3) + length(sn)

empty_place_available = lenG - lenS
current_position = 0;

sort sn randomly

loop for each sn
    rand = rand(0, empty_place_available)
    position[sn] = current_position + rand
    empty_place_available = empty_place_available - rand
    current_position = current_position + rand + length(sn)