algorithm - segment overlapping regions into disjoint regions -

given set of closed regions [a,b] a , b integers need find set of regions cover same numbers disjoint.

i suppose possible naively iterating through set several times, looking recommendation of algorithm this. please help.

edit:

to clarify, resulting regions cannot larger original ones, have come disjoint regions contained original ones. in other words, need split original regions on boundaries overlap.

example:

3,8 1,4 7,9 11,14 

result:

1,3 3,4 4,7 7,8 8,9 11,14 

(this modification of answer posted earlier today deleted after discovered had logic error. later realized modify vincent van der weele's elegant idea of using parenthesis depth fix bug)

on edit: modified able accept intervals of length 0

call interval [a,a] of length 0 essential if doesn't appear endpoint of interval of length > 0. example, in [1,3], [2,2], [3,3], [4,4] 0-length intervals [2,2] , [4,4] essential [3,3] isn't. inessential 0-length intervals redundant need not appear in final output. when list of intervals scanned (loading basic data structures) points corresponding 0-length intervals recorded, endpoint of intervals of length > 0. when scan completed, 2 instances of each point corresponding essential 0-length intervals added list of endpoints, sorted. resulting data structure multiset repetitions correspond essential 0-length intervals.

for every endpoint in interval define pdelta (parentheses delta) of endpoint number of times point appears left endpoint minus number of times appears right endpoint. store these in dictionary keyed endpoints.

[a,b] a,b first 2 elements of list of endpoints first interval in list of disjoint intervals. define parentheses depth of b sum of pdelta[a] , pdelta[b]. loop through rest of endpoints follows:

in each pass through loop @ parenthesis depth of b. if not 0 b still needed 1 more interval. let = b , let new p next value in list. adjust parentheses depth pdelta of new b , add [a,b] list of disjoint intervals. otherwise (if parenthesis depth of b 0) let next [a,b] next two points in list , adjust parenthesis depth accordingly.

here python implementation:

def disjointify(intervals):     if len(intervals) == 0: return []     pdelta = {}     ends = set()     disjoints = []     onepoints = set() #onepoint intervals     (a,b) in intervals:         if == b:             onepoints.add(a)             if not in pdelta: pdelta[a] = 0         else:             ends.add(a)             ends.add(b)             pdelta[a] = pdelta.setdefault(a,0) + 1             pdelta[b] = pdelta.setdefault(b,0) - 1     onepoints.difference_update(ends)     ends = list(ends)     in onepoints:         ends.extend([a,a])     ends.sort()     = ends[0]     b = ends[1]     pdepth = pdelta[a] + pdelta[b]     = 1     disjoints.append((a,b))     while < len(ends) - 1:         if pdepth != 0:             = b             b = ends[i+1]             pdepth += pdelta[b]             += 1         else:             = ends[i+1]             b = ends[i+2]             pdepth += (pdelta[a] + pdelta[b])             += 2         disjoints.append((a,b))     return disjoints 

sample output illustrates various edge cases:

>>> example = [(1,1), (1,4), (2,2), (4,4),(5,5), (6,8), (7,9), (10,10)] >>> disjointify(example) [(1, 2), (2, 2), (2, 4), (5, 5), (6, 7), (7, 8), (8, 9), (10, 10)]  >>> disjointify([(1,1), (2,2)]) [(1, 1), (2, 2)] 

(i using python tuples represent closed intervals though has minor drawback of looking standard mathematical notation open intervals).

a final remark: referring result collection of disjoint interval might not accurate since of these intervals have nonempty albeit 1-point intersections