1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

// @Title: 将数据流变为多个不相交区间 (Data Stream as Disjoint Intervals)
// @Author: 15816537946@163.com
// @Date: 2021-10-09 23:52:09
// @Runtime: 68 ms
// @Memory: 10.1 MB
type DisJoinSet struct {
	Set  []int
	rank []int // 用于合并优化 按秩合并
}

func Construct(n int) DisJoinSet {
	d := DisJoinSet{Set: make([]int, n), rank: make([]int, n)}
	for i := 0; i < n; i++ {
		d.Set[i] = i
	}
	return d
}

func (d *DisJoinSet) Find(x int) int {
	if d.Set[x] != x {
		// 路径压缩
		d.Set[x] = d.Find(d.Set[x])
	}
	return d.Set[x]
}

func (d *DisJoinSet) Join(x, y int) bool {
	x, y = d.Find(x), d.Find(y)
	if x != y {
		if x < y {
			// 转换 小树在前
			x, y = y, x
		}
		d.Set[y] = x
		if d.rank[x] == d.rank[y] {
			d.rank[x]++
		}
		return true
	}
	return false
}

type SummaryRanges struct {
	DisJoinSet
	exist []bool
}

func Constructor() SummaryRanges {
	return SummaryRanges{Construct(1e4 + 1), make([]bool, 1e4+1)}
}

func (this *SummaryRanges) AddNum(val int) {
	if this.exist[val] {
		return
	}
	this.exist[val] = true
	if val < 1e4 && this.exist[val+1] {
		this.Join(val, val+1)
	}
	if val > 0 && this.exist[val-1] {
		this.Join(val-1, val)
	}
}

func (this *SummaryRanges) GetIntervals() (ret [][]int) {
	for i := 0; i < 1e4; {
		if this.exist[i] {
			v := this.Find(i)
			ret = append(ret, []int{i, v})
			if v > i {
				i = v
			}
		}
		i++
	}
	return ret
}

/*
type SummaryRanges struct {
	*redblacktree.Tree
}

func Constructor() SummaryRanges {
	return SummaryRanges{redblacktree.NewWithIntComparator()}
}

func (this *SummaryRanges) AddNum(val int) {
	// 找到l0最大的且满足 l0 <= val 的区间 interval0 = [l0,r0]
	interval0, has0 := ranges.Floor(val)
    if has0 && val <- interval0.Value.(int) {
        // 情况一
        return
    }

    // 找到l1最小的且满足l1>val 的区间 interval1 = [l1,r1]
    // 在有序集合中，interval1 就是 interval0 的后一个区间
    interval1 := ranges.Iterator()
    if has0 {
        interval1 = ranges.IteratorAt(interval0)
    }
    has1 := interval1.Next()

    leftAside := has0 && interval0.Value.(int)+1 == val
    rightAside := has1 && interval1.Key().(int)-1 == val
    if leftAside && rightAside {
        // 情况四
        interval0.Value = interval1.Value().(int)
        ranges.Remove(interval1.Key())
    } else if leftAside {
        // 情况二
        interval0.Value = val
    } else if rightAside {
        // 情况三
        right := interval1.Value().(int)
        ranges.Remove(interval1.Key())
        ranges.Put(val, right)
    } else {
        // 情况五
        ranges.Put(val, val)
    }

}

func (this *SummaryRanges) GetIntervals() [][]int {
    ans := make([][]int, 0, ranges.Size())
    for it := ranges.Iterator(); it.Next(); {
        ans = append(ans, []int{it.Key().(int), it.Value().(int)})
    }
    return ans

}
*/

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddNum(val);
 * param_2 := obj.GetIntervals();
 */