区间选点

例题

区间选点-acwing

区间选点-acwing

区间问题常见解法

对于此类区间问题, 可以将区间根据左/右端点排序, 然后遍历讨论.

本题中, 我们要选择尽量少的点, 就要让我们选的点尽量覆盖多个区间. 对区间根据右端点排序后, 从最左侧的区间开始, 如果我们期望选点尽量覆盖多的区间, 就应该选择当前区间最右侧的点.

如果当前选择的点无法覆盖下一个区间, 就选择下一个区间的最右侧的点作为下一个选点.

证明:

设最小选点数量为 min, 上面方法的选点数量为 cnt, 只需要证明 min >= cnt && min <= cnt 即可.

public class acwing_905 {

    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    static Entry[] a;

    record Entry(int l, int r) implements Comparable<Entry> {
        @Override
        public int compareTo(Entry o) {
            return Integer.compare(r, o.r);
        }
    }

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine());

        a = new Entry[n];

        for (int i = 0; i < n; i++) {
            String[] nums = reader.readLine().split(" ");
            int l = Integer.parseInt(nums[0]);
            int r = Integer.parseInt(nums[1]);

            a[i] = new Entry(l, r);
        }

        Arrays.sort(a);

        int r = Integer.MIN_VALUE;
        int cnt = 0;
        for (Entry e : a) {
            if (r >= e.l) continue;

            r = e.r;
            cnt++;
        }

        System.out.println(cnt);
    }
}