AcWing 906. 区间分组

【题目描述】

AcWing 906. 区间分组

【思路】

帮助理解

import java.util.*;
class Node implements Comparable<Node>{
    int a, b;
    public Node(int aa, int bb){
        a = aa;
        b = bb;
    }
    public int compareTo(Node o){
        return this.a - o.a;
    }

}
public class Main{
    static int N = 100010;
    static Node f[] = new Node[N];
    public static void main(String args[]){
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        for(int i = 0; i < n; i++){
            int x = reader.nextInt(), y = reader.nextInt();
            f[i] = new Node(x, y);
        }
        //按左端点排序
        Arrays.sort(f, 0, n);

        Queue<Integer> minheap = new PriorityQueue<Integer>();
        for(int i = 0; i < n; i++){
            if( minheap.isEmpty() || minheap.peek() >= f[i].a ) minheap.add(f[i].b);
            else{
                //加入所有组别中右端点最小值的那个组 同时更新 
                minheap.poll();
                minheap.add(f[i].b);
            }

        }
        System.out.println(minheap.size());


    }
}