问题描述
给定一个 DAG，求一个拓扑序，使得节点 \(i\) 的拓扑序 \(\in [l_i,r_i]\)。
题解
首先进行一个预处理：对于所有 \(u\)，令 \(\forall (v,u)\in E, l_u\leftarrow \max(l_u,l_v+1),\forall (u,v)\in E, r_u\leftarrow \min(r_u,r_v-1)\)。
也就是 \(l_u\) 对任何可能的拓扑序的最小值取 \(\max\)，\(r_u\) 同理。若此时有节点 \(l_u>r_u\) 则无解。
将所有区间按 \(r\) 端点排序，然后以 \(l\) 端点为关键字插入大根堆中。从大到小依次考虑拓扑序 \(i\) 应为哪个节点，将所有 \(r_u\ge i\) 的节点插入堆中，然后取出 \(l_u\) 最大的，若 \(l_u>i\) 则显然无解，否则直接令 \(topo_i=u\)，弹堆。由贪心交换性质应该可以证明这是可能的最优情况，如果这样都无解那么一定无解。至于正确性，我们发现如果当前存在 \(j>i\) 使得 \((topo_j,topo_i)\in E\)，则会有 \(l_{topo[i]}>l_{topo[j]}\)，与每次取出 \(l\) 最大的区间矛盾。
![2022-08-20：给定区间的范围[xi,yi]，xi＜=yi，且都是正整数， 找出一个坐标集合set，set中有若干个数字， set要和每个给定的区间，有交集。 求set的最少需要几个数。 比如给](https://www.kunjuke.com/file/css/thumb/10.jpg/280-180.jpg)
![2021-10-19：缺失的区间。给定一个排序的整数数组 nums ，其中元素的范围在 闭区间 [lower, upper] 当中，返回不包含在数组中的缺失区间。力扣163。](https://www.kunjuke.com/file/css/thumb/2.jpg/280-180.jpg)