本题肯定是用差分数组(即扫描线)的思想来解。注意到,本题中的一个条件大大简化了本题的难度。因为每个线段都对应着一种unique的颜色,那么意味着所有线段的起点和终点,都会造成当前色彩集合的变动:增加一种新颜色,或者减少了一种新颜色。也就是说,任何一个题目所给线段的起点或终点,都必定会在results里生成一个新的区间。我们因此可以省去精力检查两个相邻区间是否需要合并(即色彩集合是否完全相同)。
当然,我们最终要在结果里去除那些色彩集合为空的区间,很显然,这些区间就对应着sum=0。
如果题目没有这个简化条件,相应的代码见v1。