题解 CF538H 【Summer Dichotomy】

也就是要把老师分成两组，满足每组的 $[l_i, r_i]$ 的交集，“相加”后与 $[t, T]$ 有交。 如果有三个老师的 $[l_i, r_i]$ 两两无交集，那么就完蛋了，根本没法分组。 否则，如果我们考虑其中一组的人数为 $n_1 = \min \{ r_i \}$，另一组的人数为 $n_2 = \max \{ l_i \}$。 如果 $n_1 \ge n_2$，也就是所有老师的 $[l_i, r_i]$ 两两有交的情况，那么这种情况下每个老师都可以任意选组。 如果 $n_1 < n_2$，那么这也是最“松”的一种方案了，如果 $n_1$ 增大或 $n_2$ 减小都会导致某个老师无法选组的情况。 那么，也就是说 $n_1$ 只能减小，$n_2$ 只能增大。 然而，现在 $n_1 + n_2$ 还不一定满足在 $[t, T]$ 内的情况。 所以如果 $n_1 + n_2 < t$，就只能增大 $n_2$；如果 $n_1 + n_2 > T$，就只能减小 $n_1$。 那么就可以算出最优的一个 $n_1$ 和 $n_2$ 的选取方案，再根据这个方案对老师进行一次二分图染色判定即可。 时间复杂度为 $\mathcal O (n + m)$，[评测链接](https://codeforces.com/contest/538/submission/72777616)。