# 合并区间 LeetCode 56/57 BitSet 的妙用


### 合并区间问题

以数组 `intervals` 表示若干个区间的集合，其中单个区间为 `intervals[i] = [starti, endi]` 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。 

 示例 1： 

> 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]  
> 输出：[[1,6],[8,10],[15,18]]  
> 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].


 示例 2： 

> 输入：intervals = [[1,4],[4,5]]  
> 输出：[[1,5]]  
> 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。 

 提示： 

- `1 <= intervals.length <= 10000`
- `intervals[i].length == 2 `
- `0 <= starti <= endi <= 10000`

#### 思路

看到这道题的数据这么小, 我就直接想到用`bit位`来记录每个位置是否被覆盖, 然后遍历导出, 我也确实这么做了, 但是我自己实现后实现相当复杂, 我就当时在想为什么这种需求按道理来说应该有现成的实现啊, 于是我找到了`BitSet`, 不同于`int`占用四个字节, `boolean`占用一个字节, `BitSet`粒度更细, 实现了在每个`bit位`上来记录信息, 较为高效, 列举一些常用方法:

| Modifier and Type | Method and Description                                       |
| ----------------- | ------------------------------------------------------------ |
| `void`            | `and/or/xor(BitSet set)` 与另一个`BitSet`逻辑运算所有位      |
| `int`             | `cardinality()`  返回值为`true`的数量                        |
| `void`            | `clear()`  将所有位设置为 `false`                            |
| `void`            | `clear/flip/get(int bitIndex)`  将指定位 `false`/补码/获取   |
| `void`            | `clear/flip/get(int fromIndex,  int toIndex)` 区间: `[fromIndex,toIndex)` |
| `boolean`         | `isEmpty()`  是否包含 `true`                                 |
| `int`             | `length()`  最高位的索引 + 1                                 |
| `int`             | `nextClearBit(int fromIndex)`  返回指定索引后第一个`false`位的索引 |
| `int`             | `nextSetBit(int fromIndex)`  返回指定索引后第一个`true`位的索引 |
| `int`             | `previousClearBit(int fromIndex)`/`previousSetBit(int fromIndex)` |
| `void`            | `set(int bitIndex)`  将指定索引处的位设置为 `true` <br/>`set(int bitIndex,  boolean value)`<br/>`set(int fromIndex,  int toIndex)` 区间:`[fromIndex,toIndex)`<br/>`set(int fromIndex,  int toIndex, boolean value)` |
| `int`             | `size()`  返回实际使用的空间位数                             |

那这样就相当简单了, 遍历加入所有情况, 然后遍历输出

但是注意! `[0,1]`和`[2,3]`这两个区间虽然紧挨着, 但是不可以合并, 我们需要`× 2`来保证紧挨着的区间不会合并, 我这边直接使用了位移运算, 不过复杂度其实可达`O(N^2)`

```java
public int[][] merge(int[][] intervals) {
    ArrayList<int[]> res=new ArrayList<>();
    BitSet bits=new BitSet();
    for(int[] ints:intervals)bits.set(ints[0]<<1,(ints[1]<<1)+1);
    int end=0;
    for(;;){
        int n=bits.nextSetBit(end);
        if(n==-1) break;
        end=bits.nextClearBit(n);
        res.add(new int[]{n>>1,(end-1)>>1});
    }
    return res.toArray(int[][]::new); // Java 11+ only
}
```

同上, `57`题其实可以照抄过的, 但是多了个有序条件我们可以利用一下, 复杂度 `O(N)`

```java
public int[][] insert1(int[][] intervals, int[] newInterval) {
    ArrayList<int[]> res=new ArrayList<>(intervals.length);
    BitSet bits=new BitSet();
    int last0,last1;
    final int len=intervals.length;
    if(len>=1){
        last0=intervals[0][0];
        last1=intervals[0][1];
        for(int i=1;i<len;i++){
            int now0=intervals[i][0];
            int now1=intervals[i][1];
            if(now0>last0){
                bits.set(last0<<1,(last1<<1)+1);
                last0=now0;
                last1=now1;
            }else if(now0==last0) last1=Math.max(last1,now1);
        }
        bits.set(last0<<1,(last1<<1)+1);
    }
    bits.set(newInterval[0]<<1,(newInterval[1]<<1)+1);
    int end=0;
    for(;;){
        int n=bits.nextSetBit(end);
        if(n==-1) break;
        end=bits.nextClearBit(n);
        res.add(new int[]{n>>1,(end-1)>>1});
    }
    return res.toArray(int[][]::new);
}
```

---

links:

- [56. 合并区间 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/merge-intervals/)
- [57. 插入区间 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/insert-interval/)
- [zsqw123/leetcode (github.com)](https://github.com/zsqw123/leetcode)