Readme

3009.Maximum-Number-of-Intersections-on-the-Chart

很容易看出这题需要用到扫描线。对于每一段折线相当于一段区间，我们要找出有最多重叠区间的位置。

这里需要注意的是，每个区间的端点不能都是双闭的。否则在端点处就会有重复的计数。比如"1,2,0". 如果认为有两处区间[1,2]和[0,2]，那么会认为在位置y=2处划扫描线的话可以有两个交点，但实际只有一个。对此一个比较容易想到的解决方案是，除了最后一个区间，其他所有的区间都设定为左闭右开（其中左右的定义是按照nums的先后，而不是数值的大小）。比如“1,2,0,...”，那么我们认为前两处区间[1,2)和(0,2]. 这样我们找跨越最多区间的扫描线时，就不会出错。

但是接下来还有一个问题，就是何时记录差分。对于形如[a,b)的区间，很明显，我们会在diff[a]+=1，在diff[b]-=1.而对于形如(a,b]的区间，我们可能会采用diff[a+1]+=1，在diff[b+1]-=1. 但是这样会引入一个问题。比如说"2,1,2..."，我们有两段区间分别是(1,2]和[1,2). 我们会发现，如果依据之前的差分策略，在x=1处的总diff为1，而x=2处的总diff也是1。但事实上扫描线位于[1,2]之间的位置应该能至少扫过两个交点。这就暴露了一个缺陷，我们的差分点都在整数点的位置上，但是本题里的扫描线是可以落在半整数点的位置上（比如说1.5）. 一个灵活的解决方案是，对于形如(a,b]的区间，为了反映在半整数点位置的扫描性的变化，我们可能会采用diff[a+0.5]+=1，在diff[b+0.5]-=1，也就是提早进行差分的更新。

由此得到所有的差分更新点后，走一遍积分，取全局最大值就是答案。

注意别忘了特别处理最后一个区间的右端点q，它应该被特殊处理为“闭”。所以额外单独为它额外增加一个差分点：diff[q]+=1和diff[q+0.5]-=1。