用BitSet解决重叠区间问题
力扣 56.合并区间
问题描述:
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
示例:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
比较直接的方法是根据interval左边界进行排序,然后遍历排序后的intervals。但其实也可以用BitSet直接模拟这个填充的过程:
class Solution { public int[][] merge(int[][] intervals) { BitSet bitSet=new BitSet(); int max=0; for(int[]interval:intervals){ //防止将两个连续但不重叠的区间合并到一块,进行*2映射 int l=interval[0]*2; int r=interval[1]*2; bitSet.set(l,r+1,true); max=Math.max(r,max); } int index=0; Listres=new LinkedList<>(); while(index int l=bitSet.nextSetBit(index); int r=bitSet.nextClearBit(l); index=r; res.add(new int[]{l/2,(r-1)/2}); } return res.toArray(new int[res.size()][]); } }
需要注意[0,0],[1,2]两个区间并不会合并成一个[0,2]。所以在使用BitSet时要先做一个映射,我是直接把原来的位置*2.