352. 將數據流變為多個不相交區間

給你一個由非負整數 a1, a2, …, an 組成的數據流輸入，請你將到目前為止看到的數字總結為不相交的區間列表。

實現 SummaryRanges 類：

• SummaryRanges() 使用一個空數據流初始化對象。
• void addNum(int val) 向數據流中加入整數 val 。
• int[][] getIntervals() 以不相交區間 [starti, endi] 的列表形式返回對數據流中整數的總結。

示例：輸入：
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
輸出：
[null, 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]]]解釋：
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1);      // arr = [1]
summaryRanges.getIntervals(); // 返回 [[1, 1]]
summaryRanges.addNum(3);      // arr = [1, 3]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]]
summaryRanges.addNum(7);      // arr = [1, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2);      // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]]
summaryRanges.addNum(6);      // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]

解題思路

使用優先隊列維護有序的數據流，當需要獲得不相交的區間時，我們可以遍歷優先隊列，判斷有序的數據流可以組成的不相交區間

代碼

    class SummaryRanges {PriorityQueue<Integer> pq = new PriorityQueue<>();public SummaryRanges() {}public void addNum(int val) {pq.add(val);}public int[][] getIntervals() {int pre = pq.poll(), s = pre;List<int[]> list = new ArrayList<>();while (!pq.isEmpty()) {Integer cur = pq.poll();if (cur==pre) continue;if (cur == pre + 1) {pre++;} else {list.add(new int[]{s,pre});s=pre=cur;}}list.add(new int[]{s,pre});int j=0;int[][] res=new int[list.size()][2];for (int[] ints : list) {for (int i=ints[0];i<=ints[1];i++)pq.add(i);res[j++]=ints;}return res;}}/*** Your SummaryRanges object will be instantiated and called as such:* SummaryRanges obj = new SummaryRanges();* obj.addNum(val);* int[][] param_2 = obj.getIntervals();*/