> For the complete documentation index, see [llms.txt](https://emmaguo100.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://emmaguo100.gitbook.io/leetcode/01-28-2022-56.md).

# 01/28/2022 56

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.

Time O(NLOGN)

Space O(N)

```
class Solution { 
public int[][] merge(int[][] intervals) { 
            Arrays.sort(intervals, (a,b) -> Integer.compare(a[0], b[0])); 
            LinkedList<int[]> merged = new LinkedList<>(); 
            for(int[] 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()[1] < interval[0]){ 
                                    merged.add(interval); 
                        // otherwise, there is overlap, so we merge the current and previous
                        // intervals
                        }else{ 
                                    merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]); 
                        } 
            } 
            return merged.toArray(new int[merged.size()][]);
            }
}
```