显然是一个 2-SAT 问题，相交的区间不能同时选择，但给定的区间对至少选一个。

2-SAT 需要求强连通分量，用 Kosaraju 算法，其实就是需要进行正图和反图的 DFS。正图和反图在该题中是本质相同的。对于给定的 $M$ 条边可以直接枚举，我们只需要处理区间相交的连边。

也就是我们要对于一个给定的区间，找到所有和它相交的其他区间。设区间为 $[a,b]$，我们只需要找到区间满足 $l\le b,r\ge a$。用线段树维护 $l$ 为下标 $r$ 的最大值即可。

时间复杂度 $O(N\log N+M)$。