https://cn.vjudge.net/problem/POJ-1201

题目

给定n个封闭整数区间[ai, bi]和n个整数c1，…cn。
编写一个程序:
读取区间数、它们的端点和整数c1，…， cn来自标准输入，
计算具有至少ci公共元素且区间为[ai, bi]的整数集Z的最小大小，对于每个i=1,2，…，n，
将答案写入标准输出。

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

6

分析

给定区间[a,b] 最多包含c哥点，求出交叉区间最少是多少个。
用一个res数组来记录改点是否记录并且是从终点向起点移动。

代码

package POJ;

import java.util.Scanner;

import static java.util.Arrays.sort;

public class _1201_Intervals {
    static int n;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        Interval[] jobs = new Interval[n];
        int max = -1;
        for (int i = 0; i < n; i++) {
            jobs[i] = new Interval(cin.nextInt(), cin.nextInt(), cin.nextInt());
        }
        sort(jobs);
        max = jobs[n - 1].t;//排序过后最大的在最后 t是结束位置
        int[] rec = new int[max + 1];//标记数轴上的点是否已标记
        for (int i = 0; i < n; i++) {
            int s = jobs[i].s;//起点
            int t = jobs[i].t;//终点
            int cnt = sum(rec, s, t);//找到这个区间已经选段的数量 sum[t]~sum[s-1]
            jobs[i].c -= cnt;//需要点的数量
            while ((jobs[i].c > 0)) {
                if (rec[t] == 0) {//从终点开始选点
                    rec[t] = 1;
                    jobs[i].c--;//个数减少
                    t--;//终点左移
                } else
                    t--;
            }

        }
        System.out.println(sum(rec,0,max));
    }

    private static int sum(int[] rec, int s, int t) {
        int sum = 0;
        for (int i = s; i <= t; i++) {
            sum += rec[i];
        }
        return sum;
    }

    public static class Interval implements Comparable<Interval> {
        int s, t, c;

        public Interval(int s, int t, int c) {
            this.s = s;
            this.t = t;
            this.c = c;
        }

        @Override
        public int compareTo(Interval o) {
            int x = this.s - o.s;
            if (x == 0) {
                return this.t - o.t;
            }
            return x;
        }
    }
}