# 0352. Data Stream as Disjoint Intervals

<https://leetcode.com/problems/data-stream-as-disjoint-intervals>

## Description

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:

* `SummaryRanges()` Initializes the object with an empty stream.
* `void addNum(int val)` Adds the integer `val` to the stream.
* `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**
[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]]]
**Explanation**
SummaryRanges 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:**

* `0 <= val <= 104`
* 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?

## ac

```java
class SummaryRanges {
    TreeMap<Integer, Integer> tmap;
    /** Initialize your data structure here. */
    public SummaryRanges() {
        tmap = new TreeMap<>();
    }
    
    public void addNum(int val) {
        Integer f = tmap.lowerKey(val); // floor
        Integer c = tmap.ceilingKey(val); // ceil
        // 4 situations
        if (f != null && tmap.get(f) + 1 == val && c != null && val + 1 == c) { // concatenate both
            tmap.put(f, tmap.get(c));
            tmap.remove(c);
        } else if (f != null && tmap.get(f) + 1 == val && (c == null || val + 1 < c)) { // concatenate floor
            tmap.put(f, val);
        } else if ((f == null || tmap.get(f) + 1 < val) && c != null && val + 1 == c) { // concatenate ceil
            tmap.put(val, tmap.get(c));
            tmap.remove(c);
        } else if ((f == null || tmap.get(f) + 1 < val) && (c == null || val + 1 < c)) { // independent
            tmap.put(val, val);
        }
    }
    
    public List<Interval> getIntervals() {
        List<Interval> res = new ArrayList<>();
        for (int k : tmap.keySet()) {
            res.add(new Interval(k, tmap.get(k)));
        }
        return res;
    }
}

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(val);
 * List<Interval> param_2 = obj.getIntervals();
 */

/*
1) TreeMap, key:start, value:end; 2) when adding, check floor(val) and ceil(val);  3) 5 situations: if floor.end + 1 = val and val+1 = ceil.start, concatenate and delete ceil. concatenate both, concatenate floor, concatenate ceil, independent, already in range can't add
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0352-data-stream-as-disjoint-intervals.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.