题目描述

区间合并模板题

样例

import java.util.*;
public class Main{

    static class Pair {
        int first, second;

        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }

    static void merge(ArrayList<Pair> segs) {
        ArrayList<Pair> res = new ArrayList<>();

        //按起点进行排序
         segs.sort((p1,p2) -> p1.first - p2.first);
        //segs.sort(Comparator.comparingInt(a -> a.first));

        int st = Integer.MIN_VALUE, ed = Integer.MIN_VALUE;
        for (Pair seg : segs) {
            //当前维护的区间和现在枚举出来的区间无交集
            if (ed < seg.first) {
                if (st != Integer.MIN_VALUE) res.add(new Pair(st, ed)); //System.out.println(st + " 11 " + ed);
                //System.out.println(seg.first + " 1 " + seg.second);
                st = seg.first;
                ed = seg.second;
                //System.out.println(st + " 111 " + ed);
            } else {//当前维护的区间和现在枚举出来的区间有交集
                //System.out.println(seg.first + " 2 " + seg.second);
                ed = Math.max(ed, seg.second);
            }
        }

        //为了防止segs为空（上面遍历完，把最后剩下的加进去）
        if (st != Integer.MIN_VALUE) res.add(new Pair(st, ed));

        //segs清空
        segs.clear();
        //更新区间，把res放入segs中
        segs.addAll(res);
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int max = 0, max1 = 0;
        ArrayList<Pair> segs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            segs.add(new Pair(l, r));
        }

        merge(segs);

        for(int i = 0; i < segs.size(); i++){
            max = Math.max(max,segs.get(i).second - segs.get(i).first);
            if(i < segs.size() - 1 ){
               max1 = Math.max(max1,segs.get(i + 1).first - segs.get(i).second); 
            }
        }

        System.out.println(max + " " + max1);

    }
}