Again the idea is to sort, but not only the starting points, but also the ending points. The main idea is to treat a starting point of an interval as a left parenthesis, and the ending point as a right one, and sort them independently. The algorithm goes as
- Break the pair and pool everything together into a list of parentheses.
- Sort the list according to the position of each single parenthesis.
- Read out the outer most parentheses pairs from the sorted list. Ignore any inner pairs. This is done by a linear scan assisted by some variable that records the number of outer layers for the current position.
And here is a short piece of Python code that does this:
def merge(self, intervals): list =  map(list.extend, ([(i.start, 1), (i.end, -1)] for i in intervals)) list.sort(key=lambda x:(x,-x)) n = 0; rtn =  for item in list: n += item if item == 1 and n == 1: s = item elif item == -1 and n == 0: rtn.append(Interval(s, item)) return rtn