思路
重叠性质:考虑两个区间[x1,y1] 和 [x2,y2] 重叠,等价于y1≥x2
所以我们对所有区间的左端点xi排序,从左到右遍历,判断对应的yi 是否大于等于 下一个区间的左端点xi+1 ,若重叠则合并区间yi=max(yi,yi+1) , 如此往复合并所有可能的区间 ,直到yi<xi+1 ,区间断开。
为什么要对左端点排序?贪心
对左端点排序后考虑任意一个相邻的区间[xi,yi],[xi+1,yi+1] ,它满足,选中[xi,yi]的情况下,xi≤xi+1且xi,xi+1他俩离的最近。这等价于yi 和xi+1 离的最近,那么重叠性质yi≥xi+1 最容易被满足。