区间合并讲解

用户10604450

发布于 2024-03-15 05:56:10

12200

代码可运行

文章被收录于专栏：练习两年半练习两年半

运行总次数：0

代码可运行

y总模板：

// 将所有存在交集的区间合并 void merge(vector<PII> &segs) { vector<PII> res; sort(segs.begin(), segs.end()); int st = -2e9, ed = -2e9; for (auto seg : segs) if (ed < seg.first) { if (st != -2e9) res.push_back({st, ed}); st = seg.first, ed = seg.second; } else ed = max(ed, seg.second); if (st != -2e9) res.push_back({st, ed}); segs = res; }

思路：

1.将每个区间左端点排序

2.如果下一个区间左端点大于老区间右端点，则找到了新区间，数量+1,添加新区间

否则更新较大的右端点

public static void main(String[] args) throws IOException {
        Scanner sc=new Scanner(System.in);
        int n= sc.nextInt();
        ArrayList<int []> list=new ArrayList<>();
        while (n-->0){
            int []a=new int [2];
            a[0]=sc.nextInt();
            a[1]=sc.nextInt();
            list.add(a);
        }
        System.out.println(merge(list));
    }
    public static int merge(ArrayList <int []> list){
        ArrayList <int []> newlist=new ArrayList<>();
        //对每个区间的左区间点进行升序排列
        list.sort(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });

        int l=Integer.MIN_VALUE,r=Integer.MIN_VALUE;
        for (int[] a : list) {
            //如果新的左区间大于旧的右区间
            if(a[0]>r){
                //那么意味着这是一个新区间，与原来区间不一样
                if(l!=Integer.MIN_VALUE) {
                    newlist.add(new int[]{l, r});
                }
                l=a[0];
                r=a[1];
            }else{
                r=Math.max(r,a[1]);
            }
        }
        if(l!=Integer.MIN_VALUE)  newlist.add(new int[]{l,r});
        list.clear();
        for (int[] b : newlist) {
            list.add(b);
        }
        return list.size();
    }