题目描述

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

输出最小组数。

输入格式
第一行包含整数N，表示区间数。

接下来N行，每行包含两个整数ai,bi，表示一个区间的两个端点。

输出格式
输出一个整数，表示最小组数。

样例

输入样例：
3
-1 1
2 4
3 5
输出样例：
2

第一组： [-1,1], [3,5];
第二组： [2,4]

算法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.l - e2.l);
        //通过minHeap维护每组的尾端
        Queue<Integer> minheap = new PriorityQueue<Integer>();
        for(int i = 0; i < n; ++i){
            int l = edges.get(i).l;
            int r = edges.get(i).r;
            //判断:任意组中右端点的最小值的组 >= 当前区间的的左端点L:新组
            if(minheap.isEmpty() || minheap.peek() >= l){
                minheap.add(r);
            }else{
                //可加入到老组中update 老组的 max r
                int max_r = minheap.poll();
                minheap.add(Math.max(max_r, r));
            }
        }
        System.out.print(minheap.size());
    }
}