【贪心, 二分】线段和点

题目

试题 算法提高 线段和点

---

有 $n$ 个点和 $m$ 个区间，点和区间的端点全部是整数。

对于点 $a$ 和区间 $[b,c]$ ，若 $a\ge b$ 且 $a \le c$ ，称点 $a$ 满足区间 $[b,c]$ 。

求最小的点的子集，使得所有区间都被满足。

输入

第一行两个整数 $n, m$ 。

以下 $n$ 行 每行一个整数，代表点的坐标。

以下 $m$ 行 每行两个整数，代表区间的范围。

输出

输出一行，最少的满足所有区间的点数，如无解输出 $-1$ 。

样例输入

5 5
2
6
3
8
7
2 5
3 4
3 3
2 7
6 9

样例输出

2

数据规模和约定

• $1\le n,m \le 10000$ ；
• $0 \le 点和区间的坐标 \le 50000$ 。

解题

方法一：贪心算法 二分查找

思路

贪心策略：

1. 把所有区间按照右端点升序排序，把所有点升序排序；
2. 维护 $p$ 为当前被选取的点的坐标，初始化为 $-1$ ；
3. 枚举所有区间：
   • 如果当前区间左端点大于当前选取的点 $p$ ，则说明该区间已经无法被 $p$ 满足，需要选取一个新的点来满足该区间，二分查找最后一个小于等于当前区间右端点的点：
     • 如果该点不能满足当前区间（ $p \notin [当前区间左端点, 当前区间右端点]$ ），就表明点集中已经没有点可以满足当前区间，也就是无解，直接输出 $-1$ ，退出程序。
     • 否则该点是可以满足当前区间的最优点，把 $p$ 置为该点并从点集中删除该点（注意不要改变序列的升序属性）。
   • 否则说明 $p$ 可以满足当前区间，什么也不做直接进入下一次迭代。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int n, m;
    static int[][] segs;
    static int[] pts;

    static int search(int x) {
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (pts[mid] <= x) l = mid;
            else r = mid - 1;
        }
        return r;
    }

    static void del(int idx) {
        for (int i = idx; i < n - 1; ++i) pts[i] = pts[i + 1];
        --n;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); n = (int) in.nval;
        in.nextToken(); m = (int) in.nval;
        pts = new int[n];
        segs = new int[m][2];
        for (int i = 0; i < n; ++i) {
            in.nextToken(); pts[i] = (int) in.nval;
        }
        for (int i = 0; i < m; ++i) {
            in.nextToken(); segs[i][0] = (int) in.nval;
            in.nextToken(); segs[i][1] = (int) in.nval;
        }
        Arrays.sort(segs, (a, b) -> a[1] - b[1]);
        Arrays.sort(pts);
        int p = -1, cnt = 0;
        for (int[] seg : segs) {
            int l = seg[0], r = seg[1];
            if (p < l) {
                int idx = search(r);
                p = pts[idx];
                if (p < l || p > r) {
                    System.out.println(-1);
                    return;
                }
                ++cnt;
                del(idx);
            }
        }
        System.out.println(cnt);
    }
}