题目描述

给定 N 个闭区间 [ai,bi] 请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。输出最小组数

算法分析

首先这是一个贪心的区间问题。题目的意思就是需要将这些区间分成若干组，使得分成的组数最小
按照区间的左端点进行排序。

放个图好理解一下吧。
我一开始用的是右端点排序，然后就出现了问题，不理解为什么按照左端点排序，通过图进行分析，发现按照左端点进行排序，好像很正确
至于右端点排序的话，我觉得他很适用于区间选点，或这是区最多区间不相交的数量的问题，适用于对点的求解

第一次需要先将第一个最小的放进一个组里，第二个区间，比较当前区间是否可以放进第一个组中，可以则放进，否则新建一个组
怎么判断是否可以放进去呢？ 就是把当前区间的左端点和右端点进行比较，如果当前区间的左端点大于这个组右端点，表示没有重叠。因为上一段的终点是小于下一段的起点的。放进去之后，更新这个组的右端点的最大值
放不进去的话就新建一个组，更新一下右端点，判断一下后续有没有区间可以加进来

下一个比较重要的问题就是比较了，就是当前这个区间和那一组进行比较？怎么比较

这用到的算法就比较神奇了，我觉得太秒了
采用了一个小根堆的形式，这里面的每一个值存放的是每一组的区间右端点的最大值，小根堆就是最小值在最上面，越往下值就会越大

当一个区间的左端点是小于或者等于小根堆第一个元素（也就是众多的组中区间右端点值最小的那个点），就表示这个区间连右端点最靠左的组都放不进去，那么他肯定其他的更放不进去了啊，那么我就新建一个组

如果可以放进去的话，就更新一下右端点的值，在小根堆里面表示的删除当前元素，加入新加入的元素

当把一个区间加入到一个已经存在的组的时候，在队列中删除当前组的右端点，加入新区间的右端点，此时也是一定可以保证这个右端点是会比当前queue的所有值都大，原因就是升序！

最后就是队列元素查看 删除 添加的记中方法

关于堆
在java中默认是小根堆，而且每次在堆中保存的都是一个元素，所以不需要排序即可，当存储的是一个自己新建的类时，并且含有多个元素的时候，需要进行一个堆排序，排序的方式就是在堆创建的时候加入排序方法

代码

package tanxin;

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

class PII implements Comparable<PII>{
    int x;
    int y;
    public PII(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }
    @Override
    public int compareTo(PII p) {
        // TODO Auto-generated method stub
        return this.x-p.x>0?1:-1;
    }


}

public class 区间分组 {

    /**
     * @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());
     PII x[]=new PII[n];
     for(int i=0;i<n;i++){
         String p[]=bufferedReader.readLine().split(" ");
         int l=Integer.parseInt(p[0]);
         int r=Integer.parseInt(p[1]);
         x[i]=new PII(l, r);
     }
     Arrays.sort(x);
     //按照左端点，从小到大输入完成

     Queue<Integer> minheapIntegers=new PriorityQueue<Integer>();
     //构造所有组的右端点的最小值的小根堆
     for (int j = 0; j < x.length; j++) {
         if(minheapIntegers.isEmpty() || minheapIntegers.peek() >= x[j].x){
             minheapIntegers.add(x[j].y);
         }else{
             minheapIntegers.poll();
             minheapIntegers.add(x[j].y);
         }
    }
     System.out.println(minheapIntegers.size());

    }

}