動機

這題的解法，其實是解skyline的時候，試過的解法

Problem

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

Sol

stk放所有interval

每當加入新interval時，就從最後的interval開始比，看要merge、覆蓋還是直接推進去

class Solution:
    def merge(self, ints: List[List[int]]) -> List[List[int]]:
        stk = []
        ints.sort(key=lambda x: x[0])
        for i in ints:
            while stk and i[0] <= stk[-1][1]:
                if i[1] <=stk[-1][1]: # included
                    i = stk.pop()
                else:
                    tmp = stk.pop()
                    i[0] = tmp[0]
            stk.append(i)
        return stk