[ARC076D] Exhausted?

所有人按照 $l$ 从小到大排序，依次尝试匹配从左到右每一个凳子。如果当前考虑到第 $i$ 个人，在尝试匹配从左到右第 $j$ 个凳子，且不满足 $j\le l_i$，此时 $[1,i]$ 中至少有一个人需要选择满足 $j\ge r_i$ 的凳子 $j$，显然在这些人中选择 $r_i$ 最小者一定不劣。

左侧匹配完，再把所有第一步未匹配的点按照 $r_i$ 从大到小排序，然后类似地贪心匹配。

正确性大概来源于，匈牙利算法可以以任意顺序遍历每个尚未被匹配的点，以任意顺序遍历一个点的所有出边。

---

第二种做法，先用运用霍尔定理的推论，将题意转化为，选择多条线段，求线段条数加线段交的长度最大值。

枚举线段交的左端点 $l$，此时能够选取的线段的左端点一定 $\le l$。此时对于该点右侧的每个点 $r$，它作为线段交的右端点的答案是 $r-l+k$，其中 $k$ 为完全包含 $[l,r]$ 区间的线段数量。

于是给线段树上每个点 $i$ 赋初始权值 $i$，把线段按照左端点从小到大排序，依次枚举线段 $[l,r]$，在线段树上给 $[l,r]$ 区间加一，求 $[l,+\infty)$ 区间最大值即可。