区间合并

1.AcWing 803.区间合并——模板

第一：区间排序：以每个区间的左端点排序
第二：以第一个区间作为起始区间，枚举后续每一个区间：

1.能与前一个区间合并，则合并
2.不能与前一个区间合并，则以一个新的区间开头

点击查看代码

2.AcWing 1343.挤牛奶

第一：左端点排序，然后区间合并
第二：res1记录合并后的所有区间中的最长长度
第三：res2记录区间中间的非区间段的最长长度

点击查看代码

3.AcWing 422.校门外的树

第一：区间合并，统计要移走树的数量
第二：l+1减去移走的树为剩下的树的数量

点击查看代码

4. AcWing 5407. 管道

• 二分枚举+区间合并：

  第一：秒数(答案)具有二分性：【 < k：左边秒数全未浸满，>= k：右边秒数全能浸满 】
  第二：二分枚举秒数，从左往右找第一个能浸满的秒数——时间复杂度O(logn)
  第三：check每个二分枚举的秒数，判断能否浸满——时间复杂度O(nlogn)

  check如下：
  1. 区间合并：将已经在流水的阀门在此秒数时刻浸水的长度转换为一个区间，对区间左边界排序后进行区间合并
  2. 判断：(能连续合并) 且 (合并完后区间为[1,len]) 则可以填满，反之则不能填满
  

  注意：

  1. 区间合并时，根据题意相隔一个单位也能合并，例如：[x,y]和[y+1,z]是可以合并的
  2. 二分范围很大，最大 秒数(答案) 可以为1999999999，容易爆int，**十年OI一场空，不开longlong见祖宗**
  

  总共时间复杂度：O(nlognlogn)

• 点击展示代码