algo/di-er-zhan-a01c6/tan-xin-le-9bedf/tan-xin-su-c41e8/

[giscus[bot]]

algo/di-er-zhan-a01c6/tan-xin-le-9bedf/tan-xin-su-c41e8/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》 (https://labuladong.gitee.io/algo/images/book/book_i...

https://labuladong.gitee.io/algo/di-er-zhan-a01c6/tan-xin-le-9bedf/tan-xin-su-c41e8/

[syz6]

【intervalSchedule 算法证明】

在将区间数组按区间右界升序排序后，定义以下概念：
代表区间：intvs[0] 和 执行语句 x_end = interval[1];时的 intvs[i] 是代表区间。
区间组：设代表区间 intvs[j] 是 代表区间 intvs[i] 的下一个代表区间，则 intvs[i..j - 1] 是一个区间组, intvs[i] 是该区间组的代表区间。若 intvs[i] 是最后一个代表区间，则 intvs[i..n - 1] 是一个区间组，n = intvs.length。

要证明算法，只需证明两点：

1. 任意两个代表区间不重叠
2. 对于每个区间组，组内任意两个区间重叠。

【1 任意两个代表区间不重叠】
对于任意两个代表区间 intvs[i], intvs[j], j > i，设 intvs[k] 是 intvs[j] 的前一个代表区间，i <= k < j，则 intvs[j][0] >= intvs[k][1]，又 intvs[k][1] >= intvs[i][1] （因为区间数组按区间右界升序排序），所以 intvs[j][0] >= intvs[i][1]，即 intvs[i] 与 intvs[j] 不重叠。

【2 对于每个区间组，组内任意两个区间重叠】
对于任一区间组，设其代表区间为 intvs[i]，另 end = intvs[i][1]，则 intvs[i][0] < end。对于组内任一其他区间 intvs[j], j != i，有 intvs[j][0] < end （因为 start >= x_end语句为 false），和 intvs[j][1] >= end（因为区间数组按区间右界升序排序）。所以对于组内任一区间（包括代表区间） intvs[k]，有 intvs[k][0] < end 和 intvs[k][1] >= end，即每个区间都包含区间 [end - 1, end]，所以任意两个区间都重叠。

[syz6]

以上是形式证明，也可观察文中图2，直观证明

[XiaoningChan]

452题加入了points =[[-2147483646,-2147483645],[2147483646,2147483647]]这个测试用例，导致比较器public int compare(int[] a, int[] b) {
return a[1] - b[1];
}
出错
改用Integer.compare（）能避免溢出