---
# System prepended metadata

title: 0056.Merge Intervals
tags: [Leetcode, Merge Interval, Medium]

---

#  0056.Merge Intervals
###### tags: `Leetcode` `Medium` `Merge Interval`
Link: https://leetcode.com/problems/merge-intervals/
## 思路
（这次是完全自己想的）
先对所有interval排序，首先根据interval的左端点，小的在前面，如果interval的左端点一样，那就看右端点哪个大，就哪个在前面。
然后跑loop，用现在的interval跟result里面的最后一个做比较，
如果现在的interval的左端点在result的最后一个interval里面，那么看右端点，
如果现在interval的右端点比result的最后一个interval的右端点大，那么就更新result的最后一个interval的右端点。
如果现在的interval的右端点不在result的最后一个interval里面，那么就把现在的interval加在result里面。

## Java的注意事项~
首先sort的写法，如果是给array排序（不管是几维的），可以用Arrays.sort，不需要用Collections.sort
comparator的写法是如果从小到大排就是（a,b)->(a-b)，从大到小排就是(a,b)->(b-a)

还有就是把List[int[]]转换成int[][]的方法(下面例子中res是list)
```java 
res.toArray(new int[res.size()][])
```
或者
```java
res.toArray(new int[0][])
```
后面的参数代表他要转到多大的array里面（虽然不知道为什么没有第二个参数，以及为什么第二个方法填0
## Code
```python=
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        ans = [intervals[0]]
        for i in range(1, len(intervals)):
            preInterval = ans[-1]
            currInterval = intervals[i]
            if currInterval[0]<=preInterval[1]:
                ans[-1] = [preInterval[0], max(preInterval[1], currInterval[1])]
            else:
                ans.append(currInterval)
        return ans
```
```java=
class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> ans = new ArrayList<>();
        Arrays.sort(intervals, (a,b)->(a[0]-b[0]));
        ans.add(intervals[0]);
        for(int i=1; i<intervals.length; i++){
            int[] currInterval = intervals[i];
            int[] prevInterval = ans.get(ans.size()-1);
            if(prevInterval[1]<currInterval[0]) ans.add(currInterval);
            else if(prevInterval[1]>currInterval[1]) continue;
            else{
                int l = Math.min(currInterval[0], prevInterval[0]);
                int r = Math.max(currInterval[1], prevInterval[1]);
                ans.remove(ans.size()-1);
                ans.add(new int[]{l,r});
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}
```
##  Result
Runtime: 16 ms, faster than **88.05%** of C++ online submissions for Merge Intervals.
Memory Usage: 14.2 MB, less than **80.23%** of C++ online submissions for Merge Intervals.