732. 我的日程安排表 III.md

732. 我的日程安排表 III

题目传送门

点击这里

解题思路

这道题的思路是和之前的订机票类型题很类似，就是有好多输入区间，然后计算重合次数最多的次数，这里很好用到差分思路来做，但是按照正常的数组来做结构很难定位，而且会很长，这里官方用了红黑树这个很巧妙的数据结构，每次只需要在start处+1，在end处-1即可，最后统计就行，所以这种方法主要难度在于go语言的红黑树的使用，这里红黑树的keys会按照数的大小排列。另一种数据结构的运用就是线段树这种数据结构，这里不再赘述线段树的基础结构，代码也是官方解的代码，整体写法是线段树的基本模板。

代码

type MyCalendarThree struct {
	*redblacktree.Tree
}

func Constructor() MyCalendarThree {
	return MyCalendarThree{
		redblacktree.NewWithIntComparator(),
	}
}

func (t MyCalendarThree) add(x, delta int) {
	if val, ok := t.Get(x); ok {
		delta += val.(int)
	}
	t.Put(x, delta)
}

func (this *MyCalendarThree) Book(start int, end int) int {
	this.add(start, 1)
	this.add(end, -1)

	var res int
	s := 0
	for i := this.Iterator(); i.Next(); {
		s += i.Value().(int)
		if s > res {
			res = s
		}
	}
	return res
}

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Book(start,end);
 */

type pair struct{ num, lazy int }

type MyCalendarThree map[int]pair

func Constructor() MyCalendarThree {
    return MyCalendarThree{}
}

func (t MyCalendarThree) update(start, end, l, r, idx int) {
    if r < start || end < l {
        return
    }
    if start <= l && r <= end {
        p := t[idx]
        p.num++
        p.lazy++
        t[idx] = p
    } else {
        mid := (l + r) / 2
        t.update(start, end, l, mid, idx*2)
        t.update(start, end, mid+1, r, idx*2+1)
        p := t[idx]
        p.num = p.lazy + max(t[idx*2].num, t[idx*2+1].num)
        t[idx] = p
    }
}

func (t MyCalendarThree) Book(start, end int) int {
    t.update(start, end-1, 0, 1e9, 1)
    return t[1].num
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}