有 \(n\) 个人和 \(m\) 条板凳，每个板凳只能坐一个人，第 \(i\) 个人可以坐在编号为 \([1,\ l_i]\cup[r_i,\ m]\) 的板凳，求最少会有多少个人不能坐下。

\(n,\ m\leq2\times10^5,\ 0\leq l_i<r_i\leq m+1\)

贪心，数据结构

---

如果只有 \(l_i,\ r_i\) 中的一个限制，显然可以贪心。考虑升序枚举每一个人 \(i\) ，尽量安排在左侧，若左侧没有位置了，那么考虑将已经填在左侧的右端点最小的点和 \(i\) 交换（可以用堆维护）。这个过程做完之后，将剩下的点贪心安排在右端点，因为这相当于只剩 \(r_i\) 的限制，可以直接贪心。

时间复杂度 \(O(n\log n)\)

代码

#include 
    
     using namespace std;const int maxn = 2e5 + 10;int n, m, tot, data[maxn];struct node {  int l, r;    inline bool operator < (const node &o) const {    return l < o.l || (l == o.l && r < o.r);  }} a[maxn];priority_queue