见过的经典问题
不定期更新
Q
\(n\) 个区间 \(\left [ l,r\right ]\)，给每个区间分组，使每个组内的区间两两不交，求最小的组数。
A
结论：组数 \(k\) 是合法的，当且仅当不存在一个点被所有区间覆盖 \(> k\) 次
证明：定义两个区间的偏序关系，\(b < c\) 则 \(\left [ a,b\right ]< \left [c,d\right]\)。那么问题等价于最小链覆盖，根据 Dliworth定理最小链覆盖等于最长反链。在反链中的任意两点不存在偏序关系，所以反链中的所有区间交集不为空，因为不存在一个点被覆盖 \(k\) 次，所以最长反链 \(\le k\)，即最小链覆盖 \(\le k\)。
通过这个结论，我们只需一个支持区间加，全局最大值的数据结构即可。