题目描述

blablabla

样例

blablabla

算法1

Java 代码

import java.util.*;
import java.io.*;

public class Main{

    static class Edge{
        int l;  
        int r;    
        public Edge(int l,int r){
            this.l = l;   
            this.r = r;   
        }
    }
    static List<Edge> edges;
    static int n;
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException{
        String[] s = cin.readLine().split("\\s+");
        n = Integer.parseInt(s[0]);
        edges = new ArrayList<>();
        for(int i = 0; i < n; i++){
            String[] s1 = cin.readLine().split("\\s+");
            int l = Integer.parseInt(s1[0]);
            int r = Integer.parseInt(s1[1]);
            edges.add(new Edge(l, r));
        }

        //按右端点进行排序
        edges.sort((e1, e2)-> e1.r - e2.r);
        int res = 0;
        int end = Integer.MIN_VALUE;
        for(int i = 0; i < n; ++i){
            int l = edges.get(i).l;
            int r = edges.get(i).r;
            if(l > end){
                res++;
                end = r;
            }
        }
        System.out.print(res);
    }
}