Interval Scheduling: Interval Merging
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.
Example 1:
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].
Example 2:
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 end or start are acceptable. For the clear purpose, we choose sorting by start .【Explanations for chinese in the picture】
【按start排序：sorting by start】【索引：index】
Could not load image
1
Clearly, for the merging result
x, x.startmust have the smallest start in these intersected intervals, and x.end must have the largest end in these intersected intervals as well.Could not load image
2
Since ordered,
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[0];
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 start
intervals.sort(key=lambda intv: intv[0])
res = []
res.append(intervals[0])
for i in range(1, len(intervals)):
curr = intervals[i]
# quote of the last element in res
last = res[-1]
if curr[0] <= last[1]:
# find the biggest end
last[1] = max(last[1], curr[1])
else:
# address next interval need to be merged
res.append(curr)
return res
It will be illustrated more clearly by the follow gif.
3
So far, the Interval Merging Problem have been solved.
The End. Hope this article can help you!