De-overlapping intervals

Question

I'm trying to write some code to de-overlap (open) intervals. I found inspiration in Algorithm to shift overlapping intervals until no overlap is left and Possible Interview Question: How to Find All Overlapping Intervals.

Intervals represent physical entities. Their position was estimated by some means, but this imperfect estimate results in overlapping positions of these physical entities. However, in reality these physical entities cannot occupy the same space, so I'm using this code to readjust their positions. This adjustment should move these physical entities as little as possible and maintain their estimated relative positions as much as possible. Since these are physical entities, the length of each interval cannot change.

Code works well in most cases but hangs in some cases like this:

intervals = [(0, 8), (9, 13), (11, 14), (15, 21)]

Here's my python code. Any suggestions?

def intervalLength(interval):
'''
Finds the length of an interval, supplied as a tupple
'''
return interval[1]-interval[0]

def findOverlappingIntervals(intervals):
# https://stackguides.com/questions/4542892/possible-interview-question-how-to-find-all-overlapping-intervals?rq=1
# Throw the endpoints of the intervals into an array, marking them as either start- or end-points.
# Sort them by breaking ties by placing end-points before start-points if the intervals are closed, or the other way around if they're half-open.
'''
Takes a list of intervals and returns the intervals that overlap.
List returned has nested list composed of the intervals that overlap with each other
Assumes list is ordered by the start position of the intervals
'''
end_points = []
for n,i in enumerate(intervals):
    end_points.append((i[0],'b',n)) #'b' = beginning of interval
    end_points.append((i[1],'e',n)) #'e' = end of interval
end_points.sort()
b = 0
e = 0
overlapping = [set()]
open_intervals = set()
for ep,sORe,i in end_points:
    if sORe == 'b':
        b += 1
        open_intervals.add(i)
        if b-e > 1 and i in open_intervals:
            overlapping[-1].update(open_intervals)
        elif len(overlapping[-1]) > 0:
            overlapping.append(set())
    else:
        e += 1
        open_intervals.remove(i)

overlapping = [o for o in overlapping if len(o) > 0]
overlapping = [[intervals[i] for i in o] for o in overlapping]

return overlapping

def deOverlap(intervals):
'''
Takes a list of overlapping intervals and returns a new list with updated postions
without overlap and intervals separated by 1, maintaining the previous center
'''
# Find center of overlapping intervals
avg = (reduce(lambda x,y: x+y, [a+b for a,b in intervals])+len(intervals)-1)/(len(intervals)*2.0)

# Find the total length of the ovrlapping intervals
tot_length = reduce(lambda x,y: x+y, [intervalLength(i) for i in intervals]) + len(intervals) - 1

# Find new start position for the overlapping intervals
new_start = int(round(avg-(tot_length/2.0)))

# Place first interval in new position
non_over_intervals = [(new_start, new_start+intervalLength(intervals[0]))]

# Place rest of intervals in new positions
for i in intervals[1:]:
    start = non_over_intervals[-1][1]+1
    non_over_intervals.append((start,start+intervalLength(i)))

return non_over_intervals

def deOverlapIntervals(intervals):
'''
Takes a list of intervals and returns a list with the same intervals with no overlap and
located as close to the original locations as possible
'''
non_over_intervals = intervals
i = 0
while len(findOverlappingIntervals(non_over_intervals)) > 0:
    if i >= 10000:
        print 'Tried 10,000 times and did not finish de-overlapping. Returning best I could do'
        return non_over_intervals
    overlapping_intervals = findOverlappingIntervals(non_over_intervals)
    non_over_intervals = set(non_over_intervals) - set([oi for group in overlapping_intervals for oi in group])
    for oi in overlapping_intervals:
        non_overlapping = deOverlap(oi)
        non_over_intervals.update(non_overlapping)
    non_over_intervals = list(non_over_intervals)
    non_over_intervals.sort()
    i += 1
return non_over_intervals

These intervals run fine

intervals = [(-5,-1), (0,6), (7,11), (9,14), (12,17), (21,24), (27,32), (32,36), (39,41)]

These don't. They hang because intervals keep shifting and overlapping with the left or the right end

intervals = [(0, 8), (9, 13), (11, 14), (15, 21)]

non_over_intervals = deOverlapIntervals(intervals)

Answer 1

Can't you do it a lot more simply? Like this:

result = intervals[:1]

for begin, end in intervals[1:]:
    if begin <= result[-1][1]:
        result[-1] = (result[-1][0], end)
    else:
        result.append((begin, end))

Answer 2

Like this?

intervals = [(0, 8), (9, 13), (11, 14), (15, 21)]
intervals = [list(t) for t in intervals]

for i in range(len(intervals) - 1):
    offset = intervals[i + 1][0] - intervals[i][1]
    if offset < 1:
        diff = intervals[i + 1][1] - intervals[i + 1][0]
        intervals[i + 1][0] = intervals[i][1] + 1
        intervals[i + 1][1] = intervals[i + 1][0] + diff

print(intervals)

Answer 3

I found that if shifting an interval will make it overlap with another interval, then including both the original overlapping intervals and the intervals that would overlap with the shift in a single deOverlapIntervals run will fix the problem.