AcWing 908. 最大不相交区间数量

【题目描述】

AcWing 908. 最大不相交区间数量

【思路】
1、按区间右端点升序排序
2、选取右端点t为无穷小，从前往后枚举，若该区间包含end点则直接continue（说明有交集，不是 一个不相交区间），否则选择当前区间的右端点作为t。

import java.util.Scanner;
import java.util.Arrays;
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.b - o.b;
    }

}
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);
        int res = 0, t = Integer.MIN_VALUE;
        //没有交集的区间数目
        for(int i = 0; i < n; i++){
            if( f[i].a <= t) continue;
            res ++;
            t = f[i].b;
        }
        System.out.println(res);



    }
}