g5-09161. 场次连看 未做

校园影展共安排 $n$ 场放映,第 $i$ 场从时刻 $s_i$ 开始、$t_i$ 结束。一名观众同一时刻只能看一场,且上一场结束的时刻等于下一场开始的时刻也算重叠,来不及换场。请判断能否从中选出 $k$ 场两两不重叠的放映:能输出 YES,不能输出 NO。

第一行两个整数 $n,k$。
接下来 $n$ 行,每行两个整数 $s_i,t_i$,表示一场放映的开始与结束时刻。

一行,输出 YES 或 NO。

按结束时刻排序为 $[2,3],[4,5],[6,7],[7,8],[1,10]$。依次看:$[2,3]$ 选,记录结束时刻 $3$;$[4,5]$ 开始 $4>3$,选;$[6,7]$ 开始 $6>5$,选;已选满 $3$ 场,输出 YES。注意 $[7,8]$ 的开始时刻 $7$ 等于上一场的结束 $7$,按题意属于重叠,不能连看;而若先选 $[1,10]$,它横跨全场,其余场次都看不成——这正是按开始时刻贪心会出错的原因。

$1\le k\le n\le 2\times 10^5$;$0\le s_i<t_i\le 10^9$。