0056. Merge Intervals.md

• 56- Merge Intervals
• 难度：Medium
• 相关知识点：Array | Sorting
• 题目链接：[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] overlap, 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

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals = sorted(intervals, key=lambda x:(x[0], x[1]))
        
        n = len(intervals)
        if n <= 1 : return intervals
        ans = []
        i = 0
        last_start = intervals[i][0]
        last_end = intervals[i][1]
        for i in range(1, n):
            start = intervals[i][0]
            end = intervals[i][1]
            if start <= last_end:
                last_end = max(last_end, end)
            else:
                ans.append((last_start, last_end))
                last_end = end
                last_start = start
                
        ans.append((last_start, last_end))
        return ans

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals = sorted(intervals, key=lambda x:(x[0], x[1]))
        
        n = len(intervals)
        if n <= 1 : return intervals
        ans = []
        for interval in intervals:
            if not ans or ans[-1][1] < interval[0]: #不合并
                ans.append(interval)
            else:
                ans[-1][1] = max(ans[-1][1], interval[1])
                
        return ans

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        starts = []
        ends = []
        for i in intervals:
            starts.append(i[0])
            ends.append(i[1])
        starts.sort()
        ends.sort()
        
        i = 0
        start_index = 0
        res = []
        n = len(starts)
        for i in range(n):
            if i==n-1 or starts[i+1] > ends[i]:
                res.append([starts[start_index], ends[i]])
                start_index = i + 1
        return res