最大不相交区间数量

Riicarus大约 1 分钟

最大不相交区间数量

例题

分析

同样的, 我们先将所有区间按照右端点大小从小到大排序. 从右端点最小的区间开始选取, 如果下一个区间包含了当前选取区间的右端点, 就跳过; 如果不包含, 就选取.

证明: 设最大不相交区间数量为 max, 我们选择的数量为 cnt, 只需要证明 max >= cnt && max <= cnt 即可.
max >= cnt: cnt 是不相交区间的一种选法, max 是不相交区间选法中的最大值, max >= cnt.
max <= cnt: 使用反证法, 假设 cnt 不是最佳选法, 那么还有至少一个区间可以选择. 也就是说, 如果要选取点来覆盖整个区间, cnt 个区间不足以覆盖掉, 但是我们根据上一题(区间合并)的情况, ans 个点即可覆盖. 所以, max <= 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);
    }
}

最后我们发现, 本题代码与(区间合并)的代码完全相同, 可以思考一下原因(选点覆盖与分割?).

最大不相交区间数量

# 最大不相交区间数量

# 例题

# 分析

最大不相交区间数量

例题

分析