有 \(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)\)
代码
#includeusing 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