動機

為什麼我的interval merge這麼痛苦

insight: 只要sort過的list就可以直接當heap用

Problem

Given a data stream input of non-negative integers a1, a2, ..., an, summarize the numbers seen so far as a list of disjoint intervals.

Implement the SummaryRanges class:

    t
  • SummaryRanges() Initializes the object with an empty stream.
    • t
  • void addNum(int val) Adds the integer val to the stream.
    • t
  • int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [starti, endi].

 

Example 1:

Input["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"][[], [1], [], [3], [], [7], [], [2], [], [6], []]Output[Algorithm, Leetcode, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]ExplanationSummaryRanges summaryRanges = new SummaryRanges();summaryRanges.addNum(1);      // arr = [1]summaryRanges.getIntervals(); // return [[1, 1]]summaryRanges.addNum(3);      // arr = [1, 3]summaryRanges.getIntervals(); // return [[1, 1], [3, 3]]summaryRanges.addNum(7);      // arr = [1, 3, 7]summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]]summaryRanges.addNum(2);      // arr = [1, 2, 3, 7]summaryRanges.getIntervals(); // return [[1, 3], [7, 7]]summaryRanges.addNum(6);      // arr = [1, 2, 3, 6, 7]summaryRanges.getIntervals(); // return [[1, 3], [6, 7]]

 

Constraints:

    t
  • 0 <= val <= 104
    • t
  • At most 3 * 104 calls will be made to addNum and getIntervals.

 

Follow up: What if there are lots of merges and the number of disjoint intervals is small compared to the size of the data stream?

Sol

做interval merge，但是case很多很痛苦 就是因為想在insert時做merge就很痛苦

class SummaryRanges:

    def __init__(self):
        self.stream = [] # (end,start)
        
    def addNum(self, val: int) -> None:
        if not self.stream:
            self.stream.append([val,val])
            return
        
        i = bisect_left(self.stream, [val,val])
        if i == len(self.stream):
            end, start = self.stream[-1]
            if val == end+1:
                self.stream[-1][0] = val
            elif val == end or val == start:
                pass
            else:
                self.stream.append([val,val])
        else:
            big_end, big_start = self.stream[i]
            small_end, small_start = self.stream[i-1]
            
            if small_end+1 == val and big_start-1 == val:
                self.stream[i][1] = self.stream[i-1][1]
                del self.stream[i-1]
            elif small_end+1 == val:
                self.stream[i-1][0] = val
            elif big_start-1 == val:
                self.stream[i][1] = val
            elif big_start <= val <= big_end or small_start <= val <= small_end:
                pass
            else:
                self.stream.insert(i,[val,val])

    def getIntervals(self) -> List[List[int]]:
        return [v[::-1] for v in self.stream]

這裡就全部就給heap，有趣的是只要sort過的list就可以直接當heap用 剩下就是對最後一個interval做merge就簡單多了

class SummaryRanges:

    def __init__(self):
        self.arr = []

    def addNum(self, val: int) -> None:
        heapq.heappush(self.arr, [val, val])

    def getIntervals(self) -> List[List[int]]:
        intervals = []
        
        while self.arr:
            currInterval = heapq.heappop(self.arr)
            
            if intervals and currInterval[0] <= intervals[-1][-1] + 1:
                intervals[-1][-1] = max(intervals[-1][-1], currInterval[1])
            else:
                intervals.append(currInterval)
            
        self.arr = intervals
        return self.arr