In the "Interval Scheduling: Greedy Algorithm", we use greedy algorithm to solve the interval scheduling problem, which means, given a lot of intervals, finding out the maximum subset without any overlapping.
Actually, there are many other relating problems about interval itself. Now, we will talk about the "Merge Interval Problem".
【Leetcode 56】Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
Input: [[1,3],[2,6],[8,10],[15,18]]Output: [[1,6],[8,10],[15,18]]Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Input: [[1,4],[4,5]]Output: [[1,5]]Explanation: Intervals [1,4] and [4,5] are considered overlapping.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
The general thought for solving interval problems is observing regular patterns after the sorting process.
A certain interval can be defined as
[start, end], the interval scheduling in the last article states the sorting process need to be done by
end. But for the merging problem, both sorting with the
start are acceptable. For the clear purpose, we choose sorting by
【Explanations for chinese in the picture】
【按start排序：sorting by start】【索引：index】
Clearly, for the merging result
x.startmust have the smallest
start in these intersected intervals, and
x.end must have the largest
end in these intersected intervals as well.
x.start is easy to achieve, and computing
x.end is also not difficult as well, which can take an analogy of searching the max number in a certain array.
int max_ele = arr;for (int i = 1; i < arr.length; i++)max_ele = max(max_ele, arr[i]);return max_ele;
# intervals like [[1,3],[2,6]...]def merge(intervals):if not intervals: return # ascending sorting by startintervals.sort(key=lambda intv: intv)res = res.append(intervals)for i in range(1, len(intervals)):curr = intervals[i]# quote of the last element in reslast = res[-1]if curr <= last:# find the biggest endlast = max(last, curr)else:# address next interval need to be mergedres.append(curr)return res
It will be illustrated more clearly by the follow gif.
So far, the Interval Merging Problem have been solved.
The End. Hope this article can help you!