count-integers-in-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 an empty set of intervals, implement a data structure that can:

<ul>
	<li>Add an interval to the set of intervals.</li>
	<li>Count the number of integers that are present in at least one interval.</li>
</ul>

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

<ul>
	<li><code>CountIntervals()</code> Initializes the object with an empty set of intervals.</li>
	<li><code>void add(int left, int right)</code> Adds the interval <code>[left, right]</code> to the set of intervals.</li>
	<li><code>int count()</code> Returns the number of integers that are present in at least one interval.</li>
</ul>

Note that an interval <code>[left, right]</code> denotes all the integers <code>x</code> where <code>left &lt;= x &lt;= right</code>.

&nbsp;
Example 1:

<pre>
Input
[&quot;CountIntervals&quot;, &quot;add&quot;, &quot;add&quot;, &quot;count&quot;, &quot;add&quot;, &quot;count&quot;]
[[], [2, 3], [7, 10], [], [5, 8], []]
Output
[null, null, null, 6, null, 8]

Explanation
CountIntervals countIntervals = new CountIntervals(); // initialize the object with an empty set of intervals. 
countIntervals.add(2, 3); // add [2, 3] to the set of intervals.
countIntervals.add(7, 10); // add [7, 10] to the set of intervals.
countIntervals.count(); // return 6
 // the integers 2 and 3 are present in the interval [2, 3].
 // the integers 7, 8, 9, and 10 are present in the interval [7, 10].
countIntervals.add(5, 8); // add [5, 8] to the set of intervals.
countIntervals.count(); // return 8
 // the integers 2 and 3 are present in the interval [2, 3].
 // the integers 5 and 6 are present in the interval [5, 8].
 // the integers 7 and 8 are present in the intervals [5, 8] and [7, 10].
 // the integers 9 and 10 are present in the interval [7, 10].
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= left &lt;= right &lt;= 109</code></li>
	<li>At most <code>105</code> calls in total will be made to <code>add</code> and <code>count</code>.</li>
	<li>At least one call will be made to <code>count</code>.</li>
</ul>

Count Integers in Intervals

Merge Intervals

merge-intervals

合并区间

Insert Interval

insert-interval

插入区间

Data Stream as Disjoint Intervals

data-stream-as-disjoint-intervals

将数据流变为多个不相交区间

My Calendar III

my-calendar-iii

我的日程安排表 III

Design

Segment Tree

Ordered Set

给你区间的 空 集，请你设计并实现满足要求的数据结构：

<ul>
	<li>新增：添加一个区间到这个区间集合中。</li>
	<li>统计：计算出现在 至少一个 区间中的整数个数。</li>
</ul>

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

<ul>
	<li><code>CountIntervals()</code> 使用区间的空集初始化对象</li>
	<li><code>void add(int left, int right)</code> 添加区间 <code>[left, right]</code> 到区间集合之中。</li>
	<li><code>int count()</code> 返回出现在 至少一个 区间中的整数个数。</li>
</ul>

注意：区间 <code>[left, right]</code> 表示满足 <code>left &lt;= x &lt;= right</code> 的所有整数 <code>x</code> 。

&nbsp;

示例 1：

<pre>
输入
["CountIntervals", "add", "add", "count", "add", "count"]
[[], [2, 3], [7, 10], [], [5, 8], []]
输出
[null, null, null, 6, null, 8]

解释
CountIntervals countIntervals = new CountIntervals(); // 用一个区间空集初始化对象
countIntervals.add(2, 3); // 将 [2, 3] 添加到区间集合中
countIntervals.add(7, 10); // 将 [7, 10] 添加到区间集合中
countIntervals.count(); // 返回 6
 // 整数 2 和 3 出现在区间 [2, 3] 中
 // 整数 7、8、9、10 出现在区间 [7, 10] 中
countIntervals.add(5, 8); // 将 [5, 8] 添加到区间集合中
countIntervals.count(); // 返回 8
 // 整数 2 和 3 出现在区间 [2, 3] 中
 // 整数 5 和 6 出现在区间 [5, 8] 中
 // 整数 7 和 8 出现在区间 [5, 8] 和区间 [7, 10] 中
 // 整数 9 和 10 出现在区间 [7, 10] 中</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= left &lt;= right &lt;= 109</code></li>
	<li>最多调用&nbsp; <code>add</code> 和 <code>count</code> 方法 总计 <code>105</code> 次</li>
	<li>调用 <code>count</code> 方法至少一次</li>
</ul>