분리된 구간으로서의 데이터 스트림

음수가 아닌 정수a1, a2, ..., an의 데이터 스트림 입력이 주어지면 지금까지 본 숫자를 분리된 간격 목록으로 요약합니다.
SummaryRanges 클래스를 구현합니다.

SummaryRanges() 빈 스트림으로 개체를 초기화합니다.

void addNum(int val) 정수val를 스트림에 추가합니다.

int[][] getIntervals() 현재 스트림에 있는 정수의 요약을 분리된 간격 목록으로 반환합니다[starti, endi].

예 1:

입력
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
산출
[널, 널, [[1, 1]], 널, [[1, 1], [3, 3]], 널, [[1, 1], [3, 3], [7, 7]] , 널, [[1, 3], [7, 7]], 널, [[1, 3], [6, 7]]]

설명
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1);//도착 = [1]
summaryRanges.getIntervals();//[[1, 1]] 반환
summaryRanges.addNum(3);//도착 = [1, 3]
summaryRanges.getIntervals();//[[1, 1], [3, 3]] 반환
summaryRanges.addNum(7);//도착 = [1, 3, 7]
summaryRanges.getIntervals();//[[1, 1], [3, 3], [7, 7]] 반환
summaryRanges.addNum(2);//도착 = [1, 2, 3, 7]
summaryRanges.getIntervals();//[[1, 3], [7, 7]] 반환
summaryRanges.addNum(6);//도착 = [1, 2, 3, 6, 7]
summaryRanges.getIntervals();//[[1, 3], [6, 7]] 반환

제약:

0 <= val <= 104

최대 3 * 104 호출이 addNum 및 getIntervals 로 이루어집니다.

후속 조치: 많은 병합이 있고 분리된 간격의 수가 데이터 스트림의 크기에 비해 작다면 어떻게 될까요?

해결책:

import bisect

class SummaryRanges:

    def __init__(self):
        self.nums = []
        self.dup = set()

    def addNum(self, val: int) -> None:
        if val not in self.dup:
            bisect.insort(self.nums, val)
            self.dup.add(val)

    def getIntervals(self) -> List[List[int]]:
        nums = self.nums
        n = len(nums)
        if n == 0:
            return []
        ranges = [[nums[0]]]
        for i in range(1, n):
            if nums[i] == ranges[-1][-1] or nums[i] == ranges[-1][-1] + 1:
                ranges[-1].append(nums[i])
            else:
                ranges.append([nums[i]])
        return [[r[0], r[-1]] for r in ranges]


# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(val)
# param_2 = obj.getIntervals()