data-stream-as-disjoint-intervals

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

Implement the <code>SummaryRanges</code> class:

<ul>
	<li><code>SummaryRanges()</code> Initializes the object with an empty stream.</li>
	<li><code>void addNum(int value)</code> Adds the integer <code>value</code> to the stream.</li>
	<li><code>int[][] getIntervals()</code> Returns a summary of the integers in the stream currently as a list of disjoint intervals <code>[starti, endi]</code>. The answer should be sorted by <code>starti</code>.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input
[&quot;SummaryRanges&quot;, &quot;addNum&quot;, &quot;getIntervals&quot;, &quot;addNum&quot;, &quot;getIntervals&quot;, &quot;addNum&quot;, &quot;getIntervals&quot;, &quot;addNum&quot;, &quot;getIntervals&quot;, &quot;addNum&quot;, &quot;getIntervals&quot;]
[[], [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]]
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>0 &lt;= value &lt;= 104</code></li>
	<li>At most <code>3 * 104</code> calls will be made to <code>addNum</code> and <code>getIntervals</code>.</li>
	<li>At most <code>102</code>&nbsp;calls will be made to&nbsp;<code>getIntervals</code>.</li>
</ul>

&nbsp;
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?

Data Stream as Disjoint Intervals

Summary Ranges

summary-ranges

汇总区间

Find Right Interval

find-right-interval

寻找右区间

Range Module

range-module

Range 模块

Design an Application Monitoring System

design-an-application-monitoring-system

Count Integers in Intervals

count-integers-in-intervals

统计区间中的整数数目

Design

Binary Search

Ordered Set

&nbsp;给你一个由非负整数&nbsp;<code>a1, a2, ..., an</code> 组成的数据流输入，请你将到目前为止看到的数字总结为不相交的区间列表。

实现 <code>SummaryRanges</code> 类：

<div class="original__bRMd">
<div>
<ul>
	<li><code>SummaryRanges()</code> 使用一个空数据流初始化对象。</li>
	<li><code>void addNum(int val)</code> 向数据流中加入整数 <code>val</code> 。</li>
	<li><code>int[][] getIntervals()</code> 以不相交区间&nbsp;<code>[starti, endi]</code> 的列表形式返回对数据流中整数的总结。</li>
</ul>

&nbsp;

示例：

<pre>
输入：
["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]]
</pre>

&nbsp;

提示：

<ul>
	<li><code>0 &lt;= val &lt;= 104</code></li>
	<li>最多调用&nbsp;<code>addNum</code> 和 <code>getIntervals</code> 方法 <code>3 * 104</code> 次</li>
</ul>
</div>
</div>

&nbsp;

进阶：如果存在大量合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办?