56. Merge Interval 合并区间

题目

给定一组区间 intervals，其中 intervals[i] = [starti,endi]。有些区间可能有交叠和重复，请合并所有有交叠和重复的区间。

image.png

解析

这种问题，解法是固定的，挨个扫描给定的区间，然后合并即可。问题就在于如何实现上。因为我们只需要得到最终的区间即可，我们可以考虑位运算。简单一点，我们设置一个足够大的 []bool。同时记录起始地址start 和终止地址 end。
第一次遍历时，我们将区间内所有值均设置为 true。同时更新最大值和最小值
第二次遍历，扫描这个数组，提取所有的 true 区间。

伪代码

axis = []bool
start = max
end = min

for interval range intervals
  for i range interval
    axis[i] = true


for i<end
  // 寻找起始地址
  for  i<end && axis[i] == false;i=++
  start = i
  for i<end && axis[i] == true; i++
  end = i-1
  rst = append([start,end])

代码

func merge(intervals [][]int) [][]int {
    var axis [10*10*10*10+1]bool
    start := 1<<63-1
    end := -1<<63
    var rst [][]int
    for i := range intervals {
        for x := intervals[i][0]; x <= intervals[i][1]; x++ {
            if intervals[i][0] < start {
                start = intervals[i][0]
            }
            if intervals[i][1] > end {
                end = intervals[i][1]
            }
            axis[x] = true
        }
    }
    
    for i:=start; i<=end; {
        for i<=end && axis[i] == false{
            i++
        }
        s:=i
        for i<=end && axis[i] == true {
            i++
        }
        e:=i-1
        rst = append(rst,[]int{s,e})
    }
    return rst
}

image.png

上述想法挺好的，就是忽略了一个事实情况，对于区间 [1,4] [5,6] 来说，他们在轴上是相连的，但是区间不相连。为此，我们还需要一些额外的处理。用来标识轴是否被相连的情况。
总的来说，我们将节点分为 5 种状态，空，头，尾，头尾，中
然后我们看看节点在遍历期间的转换情况。

// 0 空区域，1 头尾 2头 3尾 4 中间
// 合并情况 头节点 -> 中间节点 尾节点 -> 中间节点 头尾节点 -> 中间节点 空节点 -> 头节点，
// 空节点 头，尾，头尾 中间
// 头+头尾=头，头+头=头，头+尾=中
// 中+all = 中
// 尾+头尾=尾， 尾+头=中，尾+尾=尾，

基于次，我们调整代码，对这些复杂情况进行处理。

func merge(intervals [][]int) [][]int {
    ht:= uint8(1<<0)
    h:= uint8(1<<1)
    t:= uint8(1<<2)
    m:= uint8(1<<3)
    var axis [10*10*10*10+1]uint8
    start := 1<<63-1
    end := -1<<63
    var rst [][]int
    for i := range intervals {
        first:=intervals[i][0]
        last:=intervals[i][1]
        if first < start {
            start = first
        }
        if last > end {
            end = last
        }
        if first == last {
            if ht > axis[first] {
                axis[first] = ht
            }
            continue
        }
        if axis[first] == t {
            axis[first] = m
        }else {
            if h > axis[first] {
                axis[first]= h
            }
        }
        if axis[last] == h {
            axis[last] = m
        }else {
            if t > axis[last] {
                axis[last] = t
            }
        }
        for x := first+1; x < last; x++ {
            axis[x] = m
        }
    }
    
    var head,tail int
    for ;start<=end;start++ {
        // 判断头尾节点
        switch axis[start] {
        case ht:
            rst=append(rst,[]int{start,start})
        case h:
            head = start
        case t:
            tail = start
            rst=append(rst, []int{head,tail})
        }
    }
    return rst
}

image.png