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

链接：352.将数据流变为多个不相交区间
难度：Hard
标签：设计、二分查找、有序集合
简介：给你一个由非负整数 a1, a2, ..., an 组成的数据流输入，请你将到目前为止看到的数字总结为不相交的区间列表。

题解 1 - typescript

• 编辑时间：2021-10-09
• 执行用时：180ms
• 内存消耗：48.5MB
• 编程语言：typescript
• 解法介绍：二分插入。

class SummaryRanges {
  private set = new Set<number>();
  private list: number[] = [];
  addNum(val: number): void {
    if (this.set.has(val)) return;
    this.set.add(val);
    let l = 0;
    let r = this.list.length - 1;
    if (this.list[r] < val) {
      this.list.push(val);
      return;
    }
    while (l < r) {
      const mid = (l + r) >> 1;
      if (this.list[mid] > val) r = mid;
      else l = mid + 1;
    }
    this.list.splice(l, 0, val);
  }
  getIntervals(): number[][] {
    const ans: number[][] = [];
    for (let i = 0, l = this.list.length; i < l; i++) {
      const num = this.list[i];
      const last = ans[ans.length - 1];
      if (ans.length === 0 || last[1] + 1 < num) {
        ans.push([num, num]);
      } else {
        last[1] = num;
      }
    }
    return ans;
  }
}