This problem is easier than I thought (because it is labeled hard). Simply have two pointers. One pointing to the most recent merged interval, another pointing to the interval to come. Sorting the given collection of intervals takes O(NlogN), where N is the number of intervals we have.

```
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
if len(intervals) <= 1:
return intervals
intervals = sorted(intervals, key=lambda x: x.start)
result = [intervals[0]]
i = 0
j = 1
while j < len(intervals):
if result[i].start <= intervals[j].start and intervals[j].start <= result[i].end:
result[i] = Interval(result[i].start, max(result[i].end, intervals[j].end))
else:
result.append(intervals[j])
i += 1
j += 1
return result
```