题目描述

区间合并

JAVA代码

import java.util.*;

class Main{
    static List<Interval> intervals = new ArrayList<>();

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        for(int i =0; i< n; i++){
            intervals.add(new Interval(sc.nextInt(), sc.nextInt()));
        }

        System.out.print(merge(intervals));

    }

    static int merge(List<Interval> intervals){
        List<Interval> list = new ArrayList<>();

        //对list集合排序
        intervals.sort((i1,i2) -> Integer.compare(i1.start, i2.start));

        //第一个区间的 起始 与 结束
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;

        for(Interval i : intervals){
            //前一个区间起始 <= 后一个区间结束
            if(i.start <= end){
                //那么两个区间取 较大的.
                end = Math.max(i.end, end);
            }else{
                //否则没有交集, 直接添加 并更新头尾.
                list.add(new Interval(start,end));
                start = i.start;
                end = i.end;
            }
        }
        //最后一个区间加入.
        list.add(new Interval(start,end));
        return list.size();
    }

}

class Interval{
    int start;
    int end;
    Interval(){start = 0; end =0;}
    Interval(int a, int b){start = a; end=b;}
}