> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0056-merge-intervals.md).

# 0056. Merge Intervals

<https://leetcode.com/problems/merge-intervals>

## Description

Given an array of `intervals` where `intervals[i] = [starti, endi]`, merge all overlapping intervals, and return *an array of the non-overlapping intervals that cover all the intervals in the input*.

**Example 1:**

```
**Input:** intervals = [[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:** intervals = [[1,4],[4,5]]
**Output:** [[1,5]]
**Explanation:** Intervals [1,4] and [4,5] are considered overlapping.
```

**Constraints:**

* `1 <= intervals.length <= 104`
* `intervals[i].length == 2`
* `0 <= starti <= endi <= 104`

## ac

```java
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> res = new ArrayList<Interval>();
        // sort list
        Collections.sort(intervals, (Interval i1, Interval i2) -> {
            return i1.start - i2.start;
        });
        // dfs handle interval
        merge(intervals, 0, res);
        return res;
    }
    private void merge(List<Interval> intervals, int pos, List<Interval> res) {
        int size = intervals.size();
        if (pos >= size) return;

        int start = intervals.get(pos).start;
        int end = intervals.get(pos).end;
        for (int i = pos; i < size; i++) {
            if (i == size - 1 || intervals.get(i+1).start > end) {
                res.add(new Interval(start, end));
                merge(intervals, i+1, res);
                break;
            }
            end = Math.max(end, intervals.get(i+1).end);
        }
    }
}
```

## ac2:

```java
/**
 * 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> res = new ArrayList<Interval>();
        // edge cases
        if (intervals == null || intervals.size() <= 1) return intervals;

        // sort
        Collections.sort(intervals, (a, b) -> {return a.start - b.start;});

        // iterate list
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (Interval i : intervals) {
            if (end < i.start) {
                res.add(new Interval(start, end));
                start = i.start;
                end = i.end;
            } else {
                end = Math.max(end, i.end);
            }
        }
        // add final one
        res.add(new Interval(start, end));

        return res;
    }
}
```

## ac3:

```java
```