题目描述

主要思想

贪心中的区间问题
每一次输入的是区间的左右端点，每一次输入的一行是一组，所以可以创建pair类，用来存储区间的左右端点
pair真的很好用
真的不用每次都是用二维数组进行调度了

在pair类中需要采用Comparable接口，重构排序方法，是对区间的右端点进行排序

对区间右端点排序的原因：

需要采用的变量：就是res记录选择的点的个数

end表示区间的右端点，当经过一个不包含end的区间的时候，更新end，res++。
end的初始值应该是-1e9,不能是0，因为区间点的区间是从负1e9到1e9之间

这里的不包含指的是下一个区间的左端点严格大于end
对于区间符合的点，不需要进行任何操作可以不用判断

算法

package tanxin;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Pair implements Comparable<Pair>{
    int x;
    int y;

    public Pair(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Pair p) {
        // TODO Auto-generated method stub
        return this.y-p.y>0?1:-1;
    }



}
public class 区间选点 {

    /**905
     * @param args
     * @throws IOException 
     * @throws NumberFormatException 
     */
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(bufferedReader.readLine());
        Pair x[]=new Pair[n];
        for(int i=0;i<n;i++){
            String p[]=bufferedReader.readLine().split(" ");
            int a=Integer.parseInt(p[0]);
            int b=Integer.parseInt(p[1]);
            x[i]=new Pair(a, b);
        }
        Arrays.sort(x);

        for(int i=0;i<n;i++){
            System.out.println(x[i].x+" "+x[i].y);
        }

        int res=0;
        int end=Integer.MIN_VALUE;

        for(int i=0;i<n;i++){
            if(x[i].x > end){
                res++;
                end=x[i].y;
            }
        }
        System.out.println(res);
    }

}