# 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.``````

## Analysis

• 不能能合并 -> 就存入答案序列，下一个

• 能合并 -> 合并区间

### Intuition

If we sort the intervals by their start value, then each set of intervals that can be merged will appear as a contiguous "run" in the sorted list.

Algorithm

First, we sort the list as described. Then, we insert the first interval into our merged list and continue considering each interval in turn as follows: If the current interval begins after the previous interval ends, then they do not overlap and we can append the current interval to merged. Otherwise, they do overlap, and we merge them by updating the end of the previous interval if it is less than the end of the current interval.

## Solution

``````/**
* Definition for an interval.
* public class Interval {
*     int start;
*     int end;
*     Interval() { start = 0; end = 0; }
*     Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List<Interval> merge(List<Interval> intervals) {

List<Interval> ans = new ArrayList<>();
if (intervals == null) {
return ans;
}

intervals.sort(Comparator.comparing(i -> i.start));

Interval last = null;

for (Interval item : intervals) {
if (last  == null || last.end < item.start) {
last = item;
} else {
last.end = Math.max(last.end, item.end);
}
}
return ans;
}
}``````

Another similar implementation

``````/**
* Definition for an interval.
* public class Interval {
*     int start;
*     int end;
*     Interval() { start = 0; end = 0; }
*     Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
private class IntervalComparator implements Comparator<Interval> {
@Override
public int compare(Interval a, Interval b) {
return a.start < b.start ? -1 : a.start == b.start ? 0 : 1;
}
}

public List<Interval> merge(List<Interval> intervals) {
Collections.sort(intervals, new IntervalComparator());

for (Interval interval : intervals) {
// if the list of merged intervals is empty or if the current
// interval does not overlap with the previous, simply append it.
if (merged.isEmpty() || merged.getLast().end < interval.start) {
}
// otherwise, there is overlap, so we merge the current and previous
// intervals.
else {
merged.getLast().end = Math.max(merged.getLast().end, interval.end);
}
}

return merged;
}
}``````

## Reference

https://leetcode.com/problems/merge-intervals/solution/

Last updated