线段覆盖类问题

  • 选最少的点，使线段盖有点：线段按右端点从小到大扫，遇到没有盖有点的线段就选中右端点。
    • CSP-S 2024 T2 预处理每辆车会被哪个区间的测速仪检测到，转为如上问题。
  • 选最少的线段，使目标区间全覆盖：找到覆盖目标区间左端点且右端点最大的线段，选择该线段，缩短目标区间后重复操作。
    • NOIP-S 2010 T4 预处理在第一行某列放下一个蓄水厂后能使最后一行哪个区间有水，转为如上问题。
  • 选最多的线段，使线段两两不交：线段按右端点从小到大扫，找到一个没有相交的就计入答案。
    • ABC225E 将 7 的两端与原点连边，形成一个角。实际上一个 7 能被看到当且仅当这个角内部没有 7，转为如上问题。
  • 给线段最少分组，使得一个组中线段两两不交：按左端点排序，如果左端点比所有组的右端点都小，那么就新开一个组，否则加入右端点最小的组。
  • 选最多的线段，使点覆盖数不超过限制（P3602）。
    1. 做法一：从左到右遍历每个点，如果有点超过限制就删除覆盖它的右端点最大的线段。
    2. 做法二：将线段按左/右端点升序，按右/左端点升/降序排序，能加就加。