a
a
algo-en
english
Search
K

# Interval Scheduling: Interval Merging

Translator: GYHHAHA
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.

## First Part: Thought

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】
1
Clearly, for the merging result `x`, `x.start`must have the smallest `start` in these intersected intervals, and `x.end` must have the largest `end` in these intersected intervals as well.
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;
for (int i = 1; i < arr.length; i++)
max_ele = max(max_ele, arr[i]);
return max_ele;

## Second Part: Code

# intervals like [[1,3],[2,6]...]
def merge(intervals):
if not intervals: return []
# ascending sorting by start
intervals.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 res
last = res[-1]
if curr <= last:
# find the biggest end
last = max(last, curr)
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.