leetcode: Merge Intervals

Problem Description:

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Solution and Precautions:

Sort the intervals by the starting point, and push each interval in the sorted sequence one by one, and always check if the up coming interval overlaps the last interval in the result sequence or not, if they overlap, merge them. Keep doing this until there is no interval left. Time complexity is O(N logN).

Written on June 12, 2013