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).

Tips and Divergent thinking:



(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on June 12, 2013